2.4. О более сложных алгоритмах.

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

считая, что начальные значения заданы.

Вероятно, длина отрезка апериодичности у такой последовательности при гораздо больше, чем при . Однако теорема, аналогичная теореме 3, даже для случая не доказана.

В ряде работ рассматривались методы вида (11), представляющие собой обобщения методов и 2.2.2:

и

Все же применяются такие методы редко. Наверно компенсация за сложность этих методов по сравнению с методами вида (4) недостаточна.

2.4.2. Для получения последовательности о, можно одновременно использовать два алгоритма типа (4) с различными функциями

В счете по методу (12) почти все время используется формула и только когда кратно М, последовательность «возмущается»: . Поэтому метод этот, предложенный Д. И. Голенко, назван методом возмущений, а целое число М—периодом возмущения.

Метод возмущений увеличивает длину отрезка апериодичности по сравнению с методом (4). Вместо оценки (10) получается оценка (см. упражнение 6 гл. 1)

Однако необходимо предостеречь вычислителей от некритического применения этого метода: качество всех используемых псевдослучайных чисел должно быть проверено. Наблюдались случаи, когда по каждой из формул или вычислялись удовлетворительные псевдослучайные числа а в реализованном по этим формулам методе (12) числа оказались плохими: не проходил первый тест п. 3.2 (несмотря на то, что L было близко к

Рассмотрим рекуррентную формулу порядка

где а все остальные коэффициенты и переменные могут принимать лишь два значения — 0 или 1. Если начальные значения заданы, то (13) позволяет последовательно вычислить Случай из рассмотрения исключается. Уравнение (13) называется моноциклическим, если период Р решения равен

Нетрудно доказать, что все решения моноциклического уравнения имеют одну и ту же длину периода Р, и период их совпадает с отрезком апериодичности.

Пример. Уравнение моноциклическое Если задать начальные значения , то получим последовательность с периодом 15:

если начать со значений , то снова получим последовательность с периодом

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

Уравнение не моноциклическое. Если начать со значений то получим последовательность с периодом

а если задать начальные значения то получим последовательность, состоящую из одних единиц.

В статье Н. Цирлера [185], где исследованы важнейшие свойства уравнений (13), последовательности, порождаемые моноциклическими уравнениями, называются - последовательностями. Термин «моноциклическое уравнение» введен в [82]. В [176] описаны электронные схемы, реализующие формулы вида (13); по этим схемам построены физические датчики псевдослучайных двоичных цифр. Ибо решения моноциклических уравнений во многих отношениях ведут себя как двоичные случайные цифры (см. упражнение 7 гл 1).

Например, формула

порождает последовательности с . Проверка 600 000 цифр, получающихся при начальных значениях показала, что эти цифры удовлетворяют основным тестам п. 3.2, сформулированным применительно к двоичным цифрам (проверка выполнена Ю. Л. Левитаном).

Однако если из цифр попытаться строить -разрядные значения случайной величины у

то пригодность таких чисел, вероятно, окажется ограниченной: результаты работы Р. Таусворта [172] дают основания ожидать, что эмпирическое распределение групп

будет близким к теоретическому только при выполнении условия