Средства и методы разработки

Мне с генераторами с.ч. пришлось разобраться еще на спектруме, начиная с тех времен когда попадался какой-то интересный код или когда я пытался нарисовать звезды на экране, а получались столбцы. Во-первых я выписал ряд кодов гсч (все они были самопальщиной, за исключением генератора Elite), во-вторых, благодаря вовремя попавшей в руки брошюрке разобрался как работает линейный конгруэнтный генератор. Слов во всяких википедиях тонны, но на деле все просто. Есть текущее 

rnd-число. Сначала надо умножить его на константу. Потом прибавить другую константу. И это всё. Когда умножаешь и складываешь не надо делать это с сохранением точности, напротив, необходимо делать это всё прямиком в регистре длиной столько-то битов. Максимальное число хранимое битами это и есть m, а операция, когда ты делаешь арифметику без заботы о точности, грубо обрубая (заворачивая) результат длиной сколько-то битов регистра и есть математически mod m.

В данном случае для 16-битного регистра максимальное число хранящееся в 16 битах равно 65535, поэтому число в регистре всегда будет оставаться остатком от деления на 65535 или m = 65535.

Для 16-битного линейного конгруэнтного генератора функция выглядит так: rnd_next = (rnd * A + C) mod 65535

последнее mod m означает "работу в регистрах длиной 16". Умножение можно заменить сдвигами. Сложение можно заменить инкрементом. Для того чтобы генератор достигал максимальной последовательности в википедии написано что-то своё и может быть более правильное, но у меня в книжке условия были таковы: A должно давать остаток от деления на 4 равный 1, C должно быть нечетное. В коде Z80 это выглядит так:

LD HL, (RND)

LD D,H

LD E,L

ADD HL,HL

ADD HL,HL

ADD HL,DE ; умножили на 5 (5 mod 4 = 1)

INC HL ; +1, нечетное

LD (RND),HL

и это работает.

На псевдо-ассемблере:

mov reg, [random_value]

mul reg, 5 ; constant A

add reg, 1 ; constant C

mov [random_value], reg

"Шумит" любой линейный конгруэнтный генератор битово неравномерно. Он выдает шумовую последовательность именно не бинарных бит, а чисел (шум есть магнитуда числа). Есть генераторы (сдвиговые регистры) которые шумят всеми своими битами равномерно.

Поэтому если брать у этого генератора младшие биты то в итоге последовательность повтора будет совсем короткая.

Как это "работает" было прекрасно слышно на слух, я направлял тот или иные бит на динамик в порт #fe и слышал "случайность" бита. Самый качественный белый шум получался только из старшего бита. Младшие начинали шуметь все менее и менее, просто свистеть.

Именно поэтому взятие случайного числа отсечением бит типа and #0F (в синтаксисе языка си ... & 0x0F) - то есть оставление сколько-то младших бит будут работать хреново. Оставлять (маскировать) надо либо старшие биты, либо же аккуратно "масштабировать", съёживать, сжимать все 16 бит аккуратным делением на константу, либо умножением на инверсную ей.

Также хреновое у этого генератора спектральное распределение, пары,тройки чисел вовсе не какие попало, они стремятся выстроиться вполне узнаваемо (спектральный тест проваливается, смотри английскую wikipedia: /Linear_congruential_generator

картинка Hyperplanes of a linear congruential generator in three dimensions. )

Теперь перейдем к статье товарища http://www.azillionmonkeys.com/qed/random.html

вообще-то все что я хотел сделать это написать ответ на то что он рассказал в статье, но увлекся. Он там раскритиковал

x = rand() / (RAND_MAX / RANGE + 1);

Что такое RAND_MAX? Оно отражает число актуальных бит, выдаваемое генератором. Иногда для повышения качества (увеличения периода), генератор реализуют 32-битный, но результат перед выдачей сдвигают от старших бит к младшим, чтобы он получился 16-битный (напоминаю, самые шумные, с самым длинным периодом это старшие биты).

+1 это старый трюк, избегание деления на 0.

Если присмотреться к раскритикованному выражению выше и математически переписать его, то должно быть:

x = Range * rand() / RAND_MAX;

с вероятностью (probability) у этого выражения всё о.к.

Зная что rand() выдает числа от [0 до RAND_MAX] проверяем правую часть ф-лы: rand()/RAND_MAX: RAND_MAX/RAND_MAX = 1;

т.е. Range * 1 = Range.

Иначе говоря, она будет выдавать числа [0 до Range] с тем же распределением что и rand()

Этого и хотелось.

Следует только подобрать/скастить rvalue's так, чтоб разрядная сетка для умножения была достаточной.

Еще одно удобство в том что деление на константу RAND_MAX это на самом деле умножение на инверсную константу, нормальный компилер всегда это заменит.