Генерация случайных чисел в заданном диапазоне

[Oleg N. Cher]

Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.

/*--------------------------------- Cut here ---------------------------------*/
/* SEED_RND address */
#define SF_RND$ 0x5C76

unsigned int _Basic_RandBB (void) /* Ripped from Beta Basic */
{
__asm
  LD   D,#0
  LD   BC,(#SF_RND$)
  LD   H,C
  LD   L,#0xFD
  LD   A,B
  OR   A
  SBC  HL,BC
  SBC  A,D
  SBC  HL,BC
  SBC  A,D
  LD   E,A
  SBC  HL,DE
  JR   NC,R1$
  INC  HL
R1$:
  LD  (#SF_RND$),HL
__endasm;
} //__Basic_RandBB

/*--------------------------------- Cut here ---------------------------------*/
unsigned char Basic_RND (unsigned char min, unsigned char max) {
  return _Basic_RandBB()%(max-min+1) + min;
} //Basic_RND

/*--------------------------------- Cut here ---------------------------------*/
unsigned int Basic_RNDW (unsigned int min, unsigned int max) {
  return _Basic_RandBB()%(max-min+1) + min;
} //Basic_RNDW

Опять же, знаю, что много где в прессе и на форумах приводятся разные генераторы случ. чисел, но вопрос именно про в заданном диапазоне, так что поделитесь, пожалуйста, наработками. А можно смотреть на тему шире, не возражаю если вообще обсудим случайные, а не псевдослучайные числа и методы их получения на Z80.

[Advertiser]

[Sayman]

загляни в evo sdk, там есть rand16() на асме писанная.

[Raider]

Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.
Опять же, знаю, что много где в прессе и на форумах приводятся разные генераторы случ. чисел, но вопрос именно про в заданном диапазоне, так что поделитесь, пожалуйста, наработками. А можно смотреть на тему шире, не возражаю если вообще обсудим случайные, а не псевдослучайные числа и методы их получения на Z80.

Все задачи решает линейный конгруэнтный генератор (Linear congruential generator - см. wikipedia, также советую почитать Lehmer random number generator)
Его формула СледЧисл = (A * Число + B) MOD N

выражение (Число * A) MOD N означает остаток от деления, но если умножение и сложение реализуется с возможным переполнением ("заворотом"), то функция MOD N достигается даром. То есть если регистры восьмибитные, то N = 255, если 16-битные то N = 65535 что как раз и отвечает заданным требованиям.

Для достижения максимальной длины последовательности к A и B предъявляются определенные требования. B нечетное, A нечетное и берется таким что остаток от деления его на 4 равен 1. В статье Wikipedia условия несколько более сложные.
Этому удовлетворяют например, A=5, B=1. Тогда на ассемблере Z80 код простейшего 8-битного датчика ПСЧ получается:

SEED:  LD  A, #33   ; любое начальное значение
LD B,A
ADD A,A
ADD A,A
ADD A,B ; это умножение на 5, т.е. A=5
INC A     ; это B=1
LD (SEED+1), A

аналогично можно построить 16-битный датчик ПСЧ, используя регистровую пару.
Родной RND-генератор BASIC использует A=75 и B=1, N=65535

Теперь что касается генерации чисел в заданном диапазоне.
С сохранением статистического распределения приемлемо быстрого решения (на мой личный взгляд) нет, за исключением использования специальных алгоритмов. Самое простое это взять генератор и использовать N старших бит, получая псевдослучайые числа в диапазоне [0...N-1].

Следует учитывать что линейный конгруэнтный генеретор генерирует псевдослучайные числа, но не биты.
Поэтому биты в линейном конгруэнтном генераторе неравноценны. Наибольшая длина последовательности отражена в старших битах, поэтому использовать следует именно их, они наиболее "шумящие".

[Bedazzle]

Тогда на ассемблере Z80 код простейшего 8-битного датчика ПСЧ получается:

Пять тысяч значений ложатся так:

[Reobne]

Можем ли определить, при компиляции, являются ли аргументы константами?

[Oleg N. Cher]

При компиляции - конечно можем. А вот внутри самой процедуры - нет.

Просто мало смысла зауживать процедуру только для диапазанов-констант. Хотя эффективность для известных значений конечно может быть выше, не спорю. AND 7 вместо MOD 8, например. =) Но такую оптимизацию компилятор сам делает.

[Reobne]

Компилятор сам делает!? Тогда нет проблем!
Raider пишет что надо использовать старшие биты, так что ты свой остаток от деления замени на деление. А компилятор уже будет оптимизировать деление на константу, заменяя её сдвигами.

[Raider]

Пять тысяч значений ложатся так:

1. Это с 8-ю битами (N=255) ?
2. Что это, как построен график. Шагали по оси абсцисс и отражали по оси ординат полученное ПСЧ?

Выше это был пример. Для практической реализации надо использовать минимум N=65535

LD HL, (SEED)
LD D,H
LD E,L
ADD HL,HL
ADD HL,HL
ADD HL,DE    ; HL=HL*5
INC HL       ;  + 1
LD (SEED),HL
RET
SEED: DW 0

Для работы с длинными последовательностями следует брать минимум N=65535. Длина последовательности будет 2^16.
"качество" ПСЧ-последовательности можно простейшим способом анализировать путем взятия двух соседних отсчетов и отображения их по X,Y.
Если между X и Y существует корреляция, то точки начнут выстраиваться в какие-либо структуры (чаще полоски) и заполнение экрана будет не равномерным.
Распределение точек по экрану должно быть шумоподобное (Монте-Карло), т.е. точки должны ставиться равномерно по всей площади экрана.
В 90х годах у меня была статья по нескольким генераторам ПСЧ которые я нашел в игрушках. Скорее всего это "самоделки" программистов. Все они в той или иной степени проваливали даже описанный выше тест звездного неба.
Для реальной оценки ПСЧ существуют известные статистические тесты, например спектральный тест.

Линейный конгруэнтный генератор не идеален, имеет недостатоки (см. статью wikipedia). Однако он простейший и быстрейший, т.е. обладает необходимым балансом качеств. Сейчас существуют современные и чуть более сложные алгоритмы генераторов ПСЧ, см. https://en.wikipedia.org/wiki/List_o...ber_generators
в библиотеке такой более сложный генератор имеет смысл предлагать опционально.

[Hacker VBI]

Быстрые генераторы ПСЧ на основе LFSR

[Bedazzle]

1. Это с 8-ю битами (N=255) ?
2. Что это, как построен график. Шагали по оси абсцисс и отражали по оси ординат полученное ПСЧ?

оба ответа "да".
Разве что с поправкой, что 8 бит это 256

Выше это был пример. Для практической реализации надо использовать минимум N=65535

График добавлен как предостережение тем, кто мог набежать и невдумчиво использовать вместо серьёзного генератора.