Assembler - язык неограниченных возможностей


Генераторы случайных чисел - часть 2


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




Начало  Назад  Вперед