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




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