5.7.1. Генераторы случайных чисел

Самый часто применяемый тип алгоритмов генерации псевдослучайных пос­ледовательностей - линейные конгруэнтные генераторы, описываемые общим ре­куррентным соотношением:

= (al + с) MOD m.

При правильно выбранных числах а и с эта последовательность все числа от нуля до т-1 псевдослучайным образом и ее периодичность сказывается только на последовательностях порядка т. Такие генераторы очень легко реализу­ются и работают быстро, но им присущи и некоторые недостатки: самый младший

бит намного менее случаен, чем, например, самый старший, а также, если попытать­ся использовать результаты работы этого генератора для заполнения k-мерного про­странства, начиная с некоторого k, точки будут лежать на параллельных плоскостях. Оба недостатка можно устранить, используя так называемое перемешивание дан­ных: числа, получаемые при работе последовательности, не выводятся сразу, а по­мещаются в случайно выбранную ячейку небольшой таблицы (8-16 чисел); число, находившееся в этой ячейке раньше, возвращается как результат работы функции.

Если число а подобрано очень тщательно, может оказаться, что число с равно нулю. Так, классический стандартный генератор Льюиса, Гудмана и Мил­лера использует а = 16 807 (7s) при m = 231-1, а генераторы Парка и Миллера используют а = 48 271 и а = 69 621 (при том же т). Любой из этих генераторов

можно легко применить в ассемблере для получения случайного 32-битного чис­ла, достаточно всего двух команд - MUL и DIV.

Процедура

; Возвращает в ЕДХ случайное положителвное 32-битное число  (от 0 до 231-2).

rand      proc near

push 'edx

mov eax,dword ptr seed

test eax,eax

js fetch.seed

randomize: mul

div mov mov pop ret

fetch_seed:

push push pop

mov pop

jmp

rand_a randjn seed rand

dword ptr rand_a dword ptr. randjn eax,edx

dword ptr seed,eax

edx

ds

0O40h

ds

eax,dword ptr ds:006Ch ds

short

Считать последнее случайное число. Проверить его,  если это Л, функция еще ни разу не вызывалась и надо создать начальное значение.

Умножитв на число а.

Взять остаток от деления на 231-1.

Сохранить для следующих вызовов.

.Считать двойное слово из данных BIOS по адресу 0040:006С - текущее число тактов таймера.'

области

dd dd dd

endp

Если период этого генератора (порядка 109) окажется слишком мал, можно скомбинировать два генератора с разными а и т, не имеющими общих делителей, например: а, = 400 014 с т1 = 2 147 483 563 и а2 - 40 692 с ні - 2 147 4 8 3 399. Генератор, работающий по уравнению

=

MOD m,

где m - любое из и имеет период 2,3 х

Очевидный недостаток такого генератора - команды МИЬ и БГУ относятся к самым медленным. От БГУ можно избавиться, используя один из генераторов с ненулевым числом с и т, равным степени двойки (тогда DIV гп заменяется на

AND m-1), например: а = 25 173, с = 13849,m = 2" или а 1 664 525, с 904

т = 232, однако проще перейти к методам, основанным на сдвигах или вычитаниях.

Алгоритмы, основанные на вычитаниях, не так подробно изучены, как конгру­энтные, но из-за большой скорости широко используются и, по-видимому, не имеют заметных недостатков. Детальное объяснение алгоритма этого генератора (а также алгоритмов многих других генераторов случайных чисел) приведено в книге Кнута Д. Е. «Искусство программирования» (т. 2).

Сложные приемы программирования

Процедура 5гап<итЧ.

Инициализирует кольцевой буфер для генератора, Вход:   ЕАХ - начальное значение,  например из области

использующего вычитания.

, данных BIOS,

как в предыдущем примере.

srand_

init

proc near

 

push

bx

 

push

si

 

push

edx

 

mov

edx, 1

, Засеять кольцевой буфер.

 

mov

bx,216

do_0:

mov

word ptr ablex[bx],dx

 

sub

eax,edx

 

xchg

eax,edx

 

sub

bx,4

 

jge

do_0

, Разогреть генератор.

 

mov

bx,216

do 1 :

push

bx

do_2:

mov

si, bx

 

add

si, 120

 

cmp

si, 216

 

jbe

skip

 

sub

si, 216

skip:

mov

ptr

 

sub

eax, dword ptr tablex[si]

 

mov

dword ptr tablex[bx],eax

 

sub

bx,4

 

jge

do 2

 

pop

bx

 

sub

bx,4

 

jge

do_1

, Инициализировать индексы

 

sub

ax, ax

 

mov

word ptr indexO.ax

 

mov

ax, 124

 

mov

ax

 

pop

edx

 

pop

si

 

pop

bx

 

ret

 

srand_init

endp

Процедура srand.

Возвращает случайное 3'2-битное число і ЕАХ (от 0 до 232-1 ).

Перед первым вызовом этой процедуры должна быть один раз вызвана процедура srand_init.

srand proc near

push bx push si

Популярные алгоритмы

 

mov -

bx.word ptr indexO

 

 

mov

si,word ptr indexl

; Считать индексы.

 

mov

eax.dword   ptr tablex[bx]

 

 

sub

eax.dword ptr tablexfsi]

; Создать новое случайное число.

 

mov

dword ptr tablex[si],eax

; Сохранить его в кольцевом

 

 

 

; буфере.

 

sub

si,4

; Уменьшить индексы,

 

jl

fix_si

; перенося их на конец буфера,

fixed_si

:mov

word ptr indexl,si

; если они выходят за .начало.

 

sub

bx,4

 

 

jl

fix_bx

 

fixed_bx

:mov

indexO,bx

 

 

pop

si

 

 

pop

bx

 

 

ret

 

 

fix_SI:.

mov

Si, 216

 

 

imp'

short fixed_SI

 

fix_BX:

mov

Ьх,216

 

 

jmp

short fixed BX

 

srand

 

endp

 

tablex

 

dd         55 dup (?)

; Кольцевой буфер случайных чисе.

indexO

 

dw 7

; Индексы для  кольцевого буфера.

indexl

 

dw 9

 

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

; rand8

; Возвращает случайное 8-битное число в AL.

; Переменная seed должна быть инициализирована заранее,

; например из области данных BIOS, как в примере для конгруэнтного генератора.

rand8

 

proc

near

 

mov

ах, word

ptr seed

 

mov

cx,8

 

newbit:

mov

bx, ax

 

 

and

bx,002Dh

 

 

xor

bh.bl

 

 

clc

 

 

 

jpe

shift

 

 

stc

 

 

shift:

rcr

ax, 1

 

 

loop

newbit

 

 

mov

word ptr

seed, ax

 

mov

ah.O

 

 

ret

 

 

rand8

 

endp

 

seed

 

dw

1