§ 3. Псевдослучайные числа

Рассмотренными в предыдущем параграфе способами можно добиться надежного получения случайных чисел с квазиравномерным распределением.

Однако генерирование случайных чисел таким путем требует установки дополнительного оборудования на электронную вычислительную машину, некоторой переделки машины для обеспечения связи ее с генератором случайных чисел, а также дополнительных затрат труда на эксплуатацию и поддержание в рабочем состоянии самого генератора.

В связи с этим представляют большой практический интерес способы получения последовательностей так называемых псевдослучайных чисел, вырабатываемых электронной вычислительной машиной при помощи специальных алгоритмов. К таким способам предъявляются два основных требования: 1) получаемые последовательности чисел должны иметь статистическую структуру, в достаточной степени близкую к структуре равномерной (или квазиравномерной) совокупности, и 2) количество операций, необходимое для выработки каждого числа последовательности, не должно быть слишком большим.

Алгоритмы для получения псевдослучайных чисел, более или менее удовлетворяющие упомянутым требованиям, описаны в ряде работ по машинной математике.

Мы остановимся здесь на двух примерах таких алгоритмов, позволяющих получить представление о свойствах псевдослучайных чисел и возможности их использования для решения прикладных задач.

Псевдослучайной последовательностью называется последовательность определяемая но.

какому-либо рекуррентному правилу

так, что при она обладает статистическими свойствами последовательности независимо выбранных значений равномерно распределенной (или распределенной по другому известному закону) случайной величины.

Ниже приведен пример образования псевдослучайных последовательностей первого порядка (т. е. в ), который опробовался с помощью цифровых вычислительных машин. Известно, что таким образом можно получать удовлетворительные последовательности при порядка нескольких тысяч.

Можно получить удовлетворительные псевдослучайные последовательности большого объема, если использовать последовательности высших порядков

Первый из рассматриваемых приемов образования последовательности псевдослучайных чисел состоит в следующем.

Пусть -разрядное двоичное число

Тогда квадрат его имеет вид

Выделим средние разряды этого числа (считая четным) и положим

Как показывают статистические испытания, формируемые таким образом случайные числа имеют распределение, близкое к квазиравномерному.

Следует заметить, что описанный процесс в некоторых случаях может вырождаться (получение на некотором шаге нулей во всех разрядах, образование циклов повторяющихся последовательностей чисел

и т. д.). Поэтому необходимо принять меры, обеспечивающие отбрасывание вырождающихся реализаций в процессе решения задачи.

Более устойчивым представляется второй прием, к изложению существа которого мы и переходим.

В машине ЭДЗАК был использован такой способ генерирования псевдослучайных последовательностей. Строятся две последовательности целых чисел согласно рекуррентным соотношениям:

В качестве значения выбиралось . Числа лежащие в диапазоне были записаны в двоичной системе счисления. Затем выбиралось число получающееся из перестановкой двоичных знаков в обратном порядке.

Над числами выполняется операция сравнения или, что то же, поразрядного сложения, т. е. двоичные разряды этих чисел складываются попарно по модулю 2. Число, получающееся в результате такой операции, после приведения в диапазон (0, 1) принимается в качестве значения члена псевдослучайной последовательности.

Существуют и другие способы построения псевдослучайных последовательностей, которые были применены для вычислений на электронных цифровых машинах. Некоторые из этих способов используют для создания нерегулярности в разрядах особенности выполнения операций в тех или иных вычислительных машинах.

Способы образования псевдослучайных последовательностей, основанные на теоретико - числовых приемах, были предложены Н. М. Коробовым и И. И. Пятецким-Шапиро.

Надо отметить, что при использовании различных способов образования псевдослучайных чисел очень трудно оценить теоретически их отатистические свойства. Обычно удается использовать сравнительно небольшие участки рекуррентных последовательностей псевдослучайных чисел.

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

Наличие в вычислительной машине хорошо проверенного датчика случайных чисел всегда является предпочтительным. Псевдослучайные числа целесообразно использовать для вычислений на таких электронных цифровых машинах, для которых решение задач методом статистических испытаний случается эпизодически. Если же метод статистических испытаний применяется на данной машине систематически, по-видимому, нецелесообразно расходовать рабочее время большой цифровой машины на замену функций весьма небольшой приставки к ней — генератора случайных чисел.