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