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

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

2.1. Алгоритмы вида ...

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

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

Рис. 3.

Рис. 4.

В самом деле, если по настоящим случайным числам построить точки с координатами , то они равномерно распределены в единичном квадрате в то время как соответствующие точки, построенные по числам (4),

располагаются на кривой

Следовательно, «хорошую» последовательность может породить только такая функция график которой весьма плотно заполняет единичный квадрат. Примером такой функции может служить функция при очень больших g (рис. 4). И действительно, эта функция послужила основой для ряда методов получения псевдослучайных чисел.

Конечно, приведенное условие только необходимо, но далеко не достаточно для того, чтобы формула (4) порождала «хорошие» псевдослучайные числа.

Другая важная черта алгоритмов вида (4) — то, что при реализации их на ЭВМ они всегда порождают периодические

последовательности. В самом деле, так как в коде любой ЭВМ можно записать лишь конечное число N чисел, заключенных между нулем и единицей, то рано или поздно какое-нибудь значение совпадает с одним из предыдущих значений . Тогда в силу (4)

Пусть L — наименьшее число, удовлетворяющее (5) при некотором множество чисел называется отрезком апериодичности последовательности (4), число L — длиной отрезка апериодичности, а длиной периода (рис. 5).

Рис. 5.

Очевидно, в рассматриваемом случае отрезок апериодичности состоит из различных чисел. И обычно для расчета не рекомендуют использовать больше чем L чисел последовательности (4). Ясно также, что

Для экспериментального определения L и Р можно рекомендовать следующий алгоритм. Выбирается целое число Т (в несколько раз меньшее, чем предполагаемое значение L). Вычисляются подряд числа причем запоминаются, и все из отрезка сравниваются со всеми только окажется выполненным равенство вычисляется длина периода и число

Чтобы вычислить L, по числу вычисляется после чего читаются и сравниваются между собой две последовательности значений: при Не позднее чем при произойдет совпадение этих значений. Если совпадение произойдет при то