Assembler - язык неограниченных возможностей
Генераторы случайных чисел
Самый часто применяемый тип алгоритмов генерации псевдослучайных последовательностей — линейные конгруэнтные генераторы, описываемые общим рекуррентным соотношением:
Ij+1 = (aIj + с) MOD m
При правильно выбранных числах а и с эта последовательность возвращает все числа от нуля до m–1 псевдослучайным образом и ее периодичность сказывается только на последовательностях порядка m. Такие генераторы очень легко реализуются и работают быстро, но им присущи и некоторые недостатки: самый младший бит намного менее случаен, чем, например, самый старший, а также если попытаться использовать результаты работы этого генератора для заполнения k-мерного пространства, начиная с некоторого k, точки будут лежать на параллельных плоскостях. Оба эти недостатка можно устранить, используя так называемое перемешивание данных: числа, получаемые при работе последовательности, не выводятся сразу, а помещаются в случайно выбранную ячейку небольшой таблицы (8 – 16 чисел), а число, находившееся в этой ячейке раньше, возвращается как результат работы функции.
Если число а подобрано очень тщательно, может оказаться, что число с равно нулю. Так, классический стандартный генератор Льюиса, Гудмана и Миллера использует а = 16 807 (75) при m = 231–1, а генераторы Парка и Миллера используют а = 48 271 и а = 69 621 (при том же m). Любой из этих генераторов можно легко использовать в ассемблере для получения случайного 32-битного числа, достаточно всего двух команд — MUL и DIV.
; Процедура rand ; возвращает в ЕАХ случайное положительное 32-битное число ; (от 0 до 231-2) ; rand proc near push edx mov eax,dword ptr seed ; считать последнее ; случайное число test eax,eax ; проверить его, если это -1, js fetch_seed ; функция еще ни разу не ; вызывалась и надо создать ; начальное значение randomize: mul dword ptr rand_a ; умножить на число а, div dword ptr rand_m ; взять остаток от ; деления на 231-1 mov eax,edx mov dword ptr seed,eax ; сохранить для ; следующих вызовов pop edx ret
fetch_seed: push ds push 0040h pop ds mov eax,dword ptr ds:006Ch ; считать ; двойное слово из области pop ds ; данных BIOS по адресу ; 0040:0060 - текущее число jmp short randomize ; тактов таймера
rand_a dd 69621 rand_m dd 7FFFFFFFh seed dd -1 rand endp
Если период этого генератора (порядка 109) окажется слишком мал, можно скомбинировать два генератора с разными а и m, не имеющими общих делителей, например: a1 = 400 014 с m1 = 2 147 483 563 и а2 = 40 692 с m2 = 2 147 483 399. Генератор, работающий по уравнению
Ij+1 = (a1Ij + a2Ij) MOD m,
где m — любой из m1 и m2, имеет период 2,3 * 1018.
Очевидный недостаток такого генератора — команды MUL и DIV относятся к самым медленным. От DIV можно избавиться, используя один из генераторов с ненулевым числом с и с m, равным степени двойки (тогда DIV m заменяется на AND m–1), например: а = 25 173, с = 13 849, m = 216 или a = 1 664 525, с = 1 013 904 223, m = 232, но проще перейти к методам, основанным на сдвигах или вычитаниях.
Алгоритмы, основанные на вычитаниях, не так подробно изучены, как конгруэнтные, но они достаточно широко используются из-за своей скорости и, по-видимому, не имеют заметных недостатков. Подробное объяснение алгоритма этого генератора (а также алгоритмов многих других генераторов случайных чисел) приведено в книге Кнута Д.Е. «Искусство программирования» (т. 2).
; Процедура srand_init ; инициализирует кольцевой буфер для генератора, использующего вычитания ; ввод: ЕАХ - начальное значение, например из области ; данных 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 eax,dword ptr tablex[bx] 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 index0,ax mov ax,124 mov index1, ax pop edx pop si pop bx ret srand_init endp
; процедура srand ; возвращает случайное 32-битное число в ЕАХ (от 0 до 232-1) ; перед первым вызовом этой процедуры должна быть один раз вызвана ; процедура srand_init srand proc near push bx push si mov bx,word ptr index0 mov si,word ptr index1 ; считать индексы mov eax,dword ptr tablex[bx] sub eax,dword ptr tablex[si] ; создать новое ; случайное число mov dword ptr tablex[si],eax ; сохранить его ; в кольцевом буфере sub si,4 ; уменьшить индексы, jl fix_si ; перенося их на конец буфера, fixed_si: mov word ptr index1,si ; если они выходят ; за начало sub bx,4 jl fix_bx fixed_bx: mov index0,bx pop si pop bx ret
fix_SI: mov si,216 jmp short fixed_SI fix_BX: mov bx,216 jmp short fixed_BX srand endp
tablex dd 55 dup (?) ; кольцевой буфер случайных чисел index0 dw ? ; индексы для кольцевого буфера index1 dw ?
Часто бывает, что требуется получить всего один или несколько случайных бит, и генераторы, работающие с 32-битными числами, оказываются неэффективными. В этом случае удобно применять алгоритмы, основанные на сдвигах:
; rand8 ; возвращает случайное 8-битное число в AL, ; переменная seed должна быть инициализирована заранее, ; например из области данных BIOS, как в примере ; для конгруэнтного генератора rand8 proc near mov ax, 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,0 ret rand8 endp
