Аддитивный генератор случайных чисел

Генератор, формирующий очередное случайное число в соответствии с отношением (3), называется аддитивным:

Xn+1=(Xn+Xn-k) mod m. (3)

В трехтомнике Кнута [5] обсуждаются подобные генераторы и рекомендован следующий вариант формулы (3):

Xn+1=(Xn-24+Xn-55) mod m.(4)

Здесь n > 55, m=21, Хо, ..., Х54 — произвольные числа, среди которых есть и нечетные. При этих условиях длина периода последовательности равна 21-1 (255-1).

Для генерации первых 55 случайных чисел можно использовать один из рассмотренных выше генераторов. Возьмем датчик линейной (смешанной) конгруэнтной последовательности случайных чисел (с > 0).

;rand_add.asm - аддитивный генератор случайных чисел.

:Вход: :Х0. а. с. m ;

случайная последовательность длиной 55 значений, получаемая с помощью

программы генерации высокослучайных двоичных наборов (см. rand_mix_cong_1.asm); :N=700 - количество элементов в последовательности + 1; :L=7 - значение степени т=27. ¦.Выход: dl - значение очередного случайного числа.

.data

N=700 количество элементов в последовательности + 1

L=7 :L - значение степени т=2

т db 128 ;128=27

mm dw 256 ; 256=28

a db 9

с dw 3

;массив значений х (начальное значение х=3) длиной N+1

х db 3, N dup (Offh)

;.........

.code

:далее фрагменты из rand_mix_cong_l.asm.

хог si,si

mov ecx.54 :счетчик цикла для формирования начальной последовательности

:первое число в последовательности х=3

mov al ,x

cycl: вычисляем очередное случайное число Х=(а*Х) mod m

mul a ;а*х в ah:al

add ax.с

shrd ax.ax.L:L - значение степени т=27

хог al.al

rol ax.L ;в al случайное число

:вывод в массив х и файл - командная строка rand_mult_cong.exe > p.txt

i nc si

mov x[si].al

mov dl.al

mov ah. 02

int 21h

loop cycl

:далее продолжаем формирование случайной последовательности, но уже аддитивным методом

mov ecx,N-55

cycl 2: incsi

хог dx.dx

mov al.x[si-24]

mov dl.x[si-55]

add ax.dx

хог dx.dx

div mm

mov x[si].dl

mov ah.02

int 21h
loop eye 12
exit:

Судя по результатам, этот метод достаточно хорош. В частности, он неплох тем, что позволяет задавать длину последовательности без оглядки на значение т.

Следующий рассматриваемый нами датчик можно использовать в программах на языке ассемблера для получения случайной последовательности 0 и 1.

Программа генерации высокослучайных двоичных наборов

Для процесса генерации требуются два значения одинаковой размерности — Y и С. Значение Y будет первым в последовательности случайных чисел. Значение С играет роль маски, в соответствии с которой впоследствии будет производиться операция «исключающее ИЛИ». Генерация очередного случайного числа происходит в два этапа. На первом этапе значение Y сдвигается влево на один разряд. При этом нас интересует содержимое выдвинутого бита. Его значением устанавливается флаг eflags.cf. На втором этапе, если cf=1, то корректируем значение Y= =Y XOR С и сохраняем Y; в противном случае сохраняем сдвинутое значение в качестве очередного числа последовательности.

:rand_bin_1.asm - программа генерации высокослучайных двоичных наборов

:(сокращенный вариант).

:Вход: у. с - в соответствии с указанными выше ограничениями.

:Выход: dl - значение очередного случайного числа.

.data

Y db 35h : Obh

С db 33h :03h

. code

cycl: shl Y.I

jnc ml

mov al ,Y

xor al ,C

mov Y.al ml: :вывод на экран (в файл - командная строка rand_bih.exe > p.txt)

jmp cycl end_cycl:

Содержимое файла, в который перенаправлен вывод программы, показывает, что период последовательности достаточно удовлетворительный (при удачном подборе Y и С). Для того чтобы получить случайную последовательность 0 и 1, необходимо на каждой итерации выделять младший или старший бит очередного значения. Доработаем программу rand_bin_1.asm, чтобы продемонстрировать этот прием.

:rand_bin_2.asm - программа генерации высокослучайных двоичных наборов (полный вариант).

:Вход: у. с - в соответствии с указанными выше ограничениями.

;Выход: dl - значение очередного случайного числа.

.data

Y db 35h :0bh

С db 33h ;03h

.code

: получаем очередное значение Y

push ds

push 40h

pop ds

mov eax.dword ptr ds:006ch

pop ds

mov Y.al

xor dl.dl

mov ecx,8 Нормируем случайные 8-ми битовые наборы в регистре DL cyct: shl Y.I

jnc ml

mov a 1. Y

xor al.C

mov Y.al

jmp $+5 ;на shrd

ml: mov al ,Y

shr al.l

rcl dl.l

loop cycl

:вывод на экран (в файл - командная строка rand_bin.exe > p.txt) очередного значения

exit:

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

В заключение данной темы — высказывание Джорджа Марсальи, которое приводит Кнут : «Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно». Возможно, экспериментируя с примерами данного раздела, вы испытали подобное чувство.

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

Длина периода и длина апериодичности. Под длиной периода понимается длина максимальной, не содержащей самой себя, числовой цепочки в последовательности случайных чисел. Длина апериодичности — длина подинтервала последовательности случайных чисел, в пределах которого не встречаются одинаковые значения.

Равномерность последовательности псевдослучайных чисел. Этот критерий означает вероятность попадания значений, генерируемых датчиком случайных чисел, в каждый из m подинтервалов, на которые можно разбить весь интервал значений, генерируемых данным датчиком случайных чисел.

Стохастичность последовательности псевдослучайных чисел. Этот критерий означает определение вероятности появления единиц (нулей) в определенных п разрядах генерируемых датчиком случайных чисел.

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

Содержание раздела