Иллюстрированный самоучитель по задачам и примерам Assembler

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

Программа генерации высокослучайных двоичных наборов

Для процесса генерации требуются два значения одинаковой размерности – 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 подинтервалов, на которые можно разбить весь интервал значений, генерируемых данным датчиком случайных чисел.
  • Стохастичность последовательности псевдослучайных чисел.
    Этот критерий означает определение вероятности появления единиц (нулей) в определенных п разрядах генерируемых датчиком случайных чисел.
  • Независимость элементов псевдослучайной последовательности.
    Этот критерий определяет степень корреляции (зависимости) двух случайных величин в сгенерированной последовательности. При проведении оценки по этому критерию можно рассматривать любые, а не только рядом стоящие случайные величины последовательности.

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

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.