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

Знание некоторых принципов нередко
возмещает незнание некоторых фактов.
Гельвецкий

Важный класс вычислительных алгоритмов, востребованных на практике, — алгоритмы генерации последовательности случайных величин. По определению, последовательностью случайных чисел является последовательно формируемый массив значений, в котором каждый очередной элемент получен вне всякой связи с другими его элементами и появление этого элемента возможно с вероятностью, подчиненной некоторому закону распределения. К примеру, если появление любого числа в этой последовательности равновероятно, то говорят о равномерном законе распределения случайных чисел.
На практике в большинстве случаев применяются программные методы получения случайных чисел. На самом дел'е случайные последовательности, получаемые по некоторому алгоритму, являются псевдослучайными. Это происходит из-за того, что связь между значениями в последовательности, получаемой программным путем, обычно все-таки существует. Данное обстоятельство приводит к тому, что на каком-то этапе генерируемая последовательность чисел начинает повторяться — «входит в период». Рассмотрим несколько наиболее известных
и пригодных для практического использования программных методов генерации псевдослучайных величин (все же, понимая смысл выражения, будем по привычке и для удобства называть их случайными).

Конгруэнтный метод генерации последовательности случайных чисел

Конгруэнтный метод генерации последовательности случайных чисел получил широкое распространение. Он описан во многих источниках, но конкретных рекомендаций по его использованию на платформе Intel автор не встретил. Попытаемся устранить этот недостаток.
В основе этого метода генерации последовательности случайных чисел лежит понятие конгруэнтности. По определению, два числа А и В конгруэнтны (сравнимы) по модулю М в случае, если существует число К, при котором А-В=КМ, то есть если разность А-В делится на М, и числа А и В дают одинаковые остатки от деления на М. Например, числа 85 и 5 конгруэнтны по модулю 10, так как при делении на 10 дают остаток 5 (при К=1). В соответствии с этим методом каждое число в этой последовательности получается исходя из следующего соотношения:

Х_n+1=(аХ_n+с) mod m, где n > 0. (1)

При задании начального значения Хо, констант а и с данное соотношение однозначно определяет последовательность целых чисел X,, составленную из остатков от деления на m предыдущих членов последовательности, в соответствии с соотношением (1). Величина этих чисел не будет превышать значение т. Если каждое число этой последовательности разделить на т, то получится последовательность случайных чисел из интервала 0.1.1'. Но не спешите подставлять в это соотношение какие-либо значения. Основная трудность при использовании этого метода — подбор компонентов формулы. В зависимости от значения с различают два вида конгруэнтного метода — мультипликативный (с=0) и смешанный (с не равно 0).
Для простоты изложения будем генерировать небольшие по величине случайные числа. Это дает возможность легко отслеживать особенности работы рассматриваемых алгоритмов с использованием стандартной возможности перенаправления ввода-вывода. Для этого необходимо, чтобы текст программы содержал строки:

movdl .ah
mov ah.02
int 21h

Запуск программы производиться командной строкой вида:

prog.exe > p.txt

При этом создается файл p.txt, в который и выводятся результаты работы программы. Если не использовать этой возможности, то вывод будет производиться на экран, что не очень удобно для последующего анализа получающейся последовательности случайных чисел. Более подробно о возможностях работы с файлами и экраном читайте материал в главах 5 и 7, посвященных работе с файлами и консолью из программ на языке ассемблера.
Большинство представленных ниже программ функционируют в бесконечном цикле, с тем, чтобы можно было изучать периодичность последовательности, создаваемой по тому или иному методу генерации случайных чисел. Поэтому для окончания работы программы ее необходимо завершить принудительно (при работе в Windows для этого можно просто закрыть окно DOS). В результате работы программы будет создан файл p.txt, который можно открыть в любом редакторе, допускающем просмотр файлов в шестнадцатеричном виде (например, встроенном редакторе файлового менеджера Windows Commander).
Для увеличения диапазона необходимо внести соответствующие, не принципиальные с точки зрения алгоритма, изменения в тексты программ.

Мультипликативный конгруэнтный метод генерации последовательности случайных чисел

Мультипликативный конгруэнтный метод задает последовательность неотрицательных целых чисел Xj (Xj<m), получаемых по формуле:

Х_n+1=аХ_n(mod m). (2)

На значения накладываются ограничения:

Хо — нечетно;
а=5^2р+1 (р=0, 1, 2, ...) или a=2^m+3 (m=3, 4, 5, ...) — обе эти записи означают, что младшая цифра а при представлении а в восьмеричной системе счисления должна быть равна 3 или 5 (проще говоря, остаток от деления а/8 должен быть равен 3 или 5);
m=2 (1>4).

При соблюдении этих ограничений, длина периода будет равна m/4.

:randjnult_cong_l.asm - датчик линейной (мультипликативной) :конгруэнтной последовательности случайных чисел (с=0).
:Вход: Хо. a, m - в соответствии с указанными выше ограничениями. .-Выход: dl - значение очередного случайного числа.

.data
in db 128
a db 11
х db 3 начальное значение
.code
;первое число в последовательности х-3
cycl: moval.x вычисляем очередное случайное число Х=(а*Х) mod in
mul а :а*х в ah:al
divm ;в ah случайное число
mov x.ah ;вывод в файл - командная строка rand_mu1t_cong.exe > p.txt
mov dl .ah
mov ah.02
nit г»
jmp cyc1
end cycl:

Если m является степенью 2, как в данном случае, то вместо команды DIV мож-, но использовать две команды сдвига.

;----------------------------------------------------------
;rand_mult_cong_2.asm - датчик линейной (мультипликативной) конгруэнтной последовательности
;случайных чисел (c=0).
;Вход: X0, a, m - в соответствие с указанными выше ограничениями.
;Выход: dl - значение очередного случайного числа.
;----------------------------------------------------------
masm
model small
.486
.data
m db 128 ;128=27
a db 11
x db 3 ;начальное значение
.stack 256
.486
.code
main:
mov dx,@data
mov ds,dx
xor dx,dx
mov cl,7 ;значение степени m=27 в cl
;первое число в последовательности x=3
cycl:
;вычисляем очередное случайное число X=(a*X) mod m
mov al,x
mul a ;a*x в ah:al
shrd ax,ax,cl
xor al,al
rol ax,cl ;в al случайное число
;вывод в файл - командная строка rand_mult_cong.exe > p.txt
mov x,al
mov dl,al
mov ah,02
int 21h
jmp cycl
end_cycl:
mov ax,4c00h
int 21h
end main

Используя эти программы, можно получить последовательность случайных чисел, содержащую 32 значения — это ее период. Чтобы увеличить период, необходимо каким-либо способом сгенерировать значения а или х, удовлетворяющие приведенным выше ограничениям. Так, значение а можно вычислить, используя фрагмент:

.data
:.........
divider db 8

.code
вычисляем а исходя из соотношения:
:а mod 8=5
:одним из способов получить значение а (т > а)
удовлетворяем условию a mod 8 = 5
m2: mov al .a
xor ah,ah
div divider
cmp ah,5 :остаток 5?
je ml
cmp ah,3 :остаток 3?
je ml
inc a
jmp m2 ml: ;теперь а найдено до конца

Изменить (увеличить) период можно, корректируя значение т, для чего необходимо будет исправить соответствующие команды в программах rand_mult_ cong_l.asm и rand_mult_cong_2.asm, ориентированные на определенную разрядность регистров. Существует другая возможность увеличения периода — использование смешанного конгруэ}1т)юго метода генерации последовательности случайных чисел.

Смешанный конгруэнтный метод генерации последовательности случайных чисел

Соотношение смешанного конгруэнтного метода выглядит так: X_n+1=(aX_n+c) mod m, где n > 0.
При правильном подборе начальных значений элементов кроме увеличения периода последовательности случайных чисел уменьшается корреляция (зависимость) получаемых случайных чисел.

На значения накладываются ограничения:

Х₀>0;
а=2¹+1, где 1>=2;
с>0 взаимно просто с m (это выполнимо, если с — нечетно, а т=2^р, где (р>=2)
m=2^р (р>=2) и т кратно 4.

:rand_mix_cong_l.asm - датчик линейной (смешанной)
:конгруэнтной последовательности случайных чисел (с>0).
:Вход: Хо. а. с. m - в соответствии с указанными выше
ограничениями.
:Выход: dl - значение очередного случайного числа.
.data
m db 128 ; 128=27
a db 9
х db 3 начальное значение
с dw 3
.code
mov cl.7 :значение степени m=27 в cl ;первое число в последовательности х=3 cycl: вычисляем очередное случайное число Х=(а*Х) mod m
mov al.x
mul a :a*x в ah:al
add ax,с
shrd ax.ax.cl
xor al.al
rol ax.cl :b al случайное число :вывод в файл - командная строка rand_mult_cong.exe > p.txt
end_cycl:

Величина периода случайной последовательности, получаемой с помощью данной программы, составляет 128 значений. Сегмент кода программы rand_mix_ cong_1.asm можно оформить в виде процедуры. Начальное значение Хо можно выбирать двумя способами: задавать константой в программе или генерировать случайным образом. В последнем случае можно использовать такты системного таймера, как в следующей макрокоманде:

rCMOS macro
макрокоманда чтения значений CMOS
:на входе: al адрес ячейки, значение которой читаем
:на входе-выходе: al - прочтенное значение
out 70h,al
хог ах,ах :вводим в регистр AL из порта значение ячейки cmos
in al.71h
endm .code
:получить значение секунд из CMOS для x_start mov al.00 rCMOS mov x.al :x=x_start

Таким способом можно получить начальное значение из диапазона 0..59. Для получения большего по величине начального значения можно использовать величину размером 32 бита из области данных BIOS по адресу 0040:006с. Здесь содержится счетчик прерываний от таймера. Извлечь это значение можно, используя следующий программный фрагмент:

push ds
push 40h
pop ds
mov eax.dword ptr ds:006ch
popds

Заменяя команду MOV командами MOV AX,word ptr ds:006ch или MOV AL, byte ptr ds:006ch, можно использовать младшие 8 или 16 бит значения из этой области BIOS. Команда MOV AL, byte ptr ds:006ch позволяет случайным образом получить в регистре AL значение из диапазона 00.. f fh.
Попытки создать программный датчик случайных чисел без опоры на какую-либо теорию обречены на провал. Рассмотрим еще несколько способов генерации случайных чисел.

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

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

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

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

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

Здесь n > 55, m=2¹, Х_о, ..., Х₅₄ — произвольные числа, среди которых есть и нечетные. При этих условиях длина периода последовательности равна 2¹-1 (2⁵⁵-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 подинтервалов, на которые можно разбить весь интервал значений, генерируемых данным датчиком случайных чисел.
Стохастичность последовательности псевдослучайных чисел. Этот критерий означает определение вероятности появления единиц (нулей) в определенных п разрядах генерируемых датчиком случайных чисел.
Независимость элементов псевдослучайной последовательности. Этот критерий определяет степень корреляции (зависимости) двух случайных величин в сгенерированной последовательности. При проведении оценки по этому критерию можно рассматривать любые, а не только рядом стоящие случайные величины последовательности.

Более подробную информацию о подходах к оценке случайных последовательностей можно получить в литературе.

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий