2.2. Некоторые конкретные алгоритмы.

2.2.1. Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют

методом середины квадрата (middle-square method). В этом методе число предполагается -значным:

Чтобы получить число , надо возвести в квадрат

и затем отобрать средние цифр этого квадрата:

Нетрудно проверить, что этому методу соответствует функция

или, что то же,

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

Наибольшее распространение получил алгоритм, предложенный Д. Лемером, который называют методом вычетов (residual method) или методом сравнений (congruential method). В этом методе , т. е.

где g — большое целое число.

Докажем, что если задать в форме несократимой дроби , где и М — целые числа, и М взаимно просто с g, то все будут несократимыми дробями вида где числители определяются формулой

Запись (7) означает, что равно остатку, полученному при делении на М (или, другими словами, это наименьший положительный вычет по модулю М).

Доказательство (по индукции). Пусть несократимая дробь . Из (7) следует, , где — целое число. Легко видеть, что взаимно просто с М В самом деле, если допустить, что и М есть общий множитель — простое число должно делиться на но g делиться на h не может, так как g взаимно просто с поэтому должно делиться на h число а это противоречит предположению о том, что несократимая дробь. Итак, взаимно просто с М и

На практике обычно используют формулу (7). Изучению последовательностей посвящено много работ. Методами теории чисел удалось исследовать длину отрезка апериодичности (см. упражнение 5 гл. 1) и оценить некоторые величины, аналогичные коэффициентам корреляции между между и т. п. Однако вопрос о пригодности таких псевдослучайных чисел в конечном счете решается обычными статистическими тестами § 3, т. е. эмпирически. При некоторых получаются удовлетворительные последовательности, при доугих — плохие. (См. также гл. 7, п. 3.3.)

Удовлетворительная последовательность псевдослучайных чисел получается, например, при результаты статистической проверки этих чисел приведены в [171].

Обширная литература, посвященная методу сравнений, имеется в [69, 139, 140]. Ряд статей с указанием недостатков метода перечислен в [180].

2.2.3. В качестве примера нелинейного алгоритма, использующего некоторые особенности системы команд ЭВМ, рассмотрим алгоритм, предложенный автором книги для ЭВМ «Стрела». В этом алгоритме число получается из числа тремя командами:

1) число умножается на большую константу

2) изображение произведения в ячейке ЭВМ сдвигается на разрядов влево;

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

Удовлетворительная последовательность псевдослучайных чисел получается, например, при результаты статистической проверки этих чисел приведены в [75].

Чтобы пояснить этот алгоритм, необходимо указать, что в ЭВМ «Стрела» числа представляются в нормализованной двоичной форме где порядок числа, мантисса Ячейка ЭВМ, в которую записывается число состоит из 43 двоичных разрядов (рис 6).

Рис. 6.

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

двоичной записи

Если произведению соответствует ячейка , то после операции сдвига получаем . Абсолютная величина этого числа в двоичной записи равна

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

2.2.4. Для получения псевдослучайных чисел на различных ЭВМ используют весьма разнообразные алгоритмы, подобные изложенному в п. 2.2.3, которые иногда называют способами перемешивания. Сведения о них имеются в [19, 69]. К сожалению, описание алгоритмов далеко не всегда сопровождается указанием количества проверенных чисел и тестов, которым эти числа удовлетворяют, или хотя бы указанием работ, в которых имеются данные о таких проверках.

Например, некоторое распространение получил трехкомандный алгоритм, разработанный Д И. Голенко для той же ЭВМ «Стрела». Однако позднее сам автор алгоритма обнаружил ([19], стр. 117), что получаемые этим методом числа плохо удовлетворяют одному из важнейших тестов — проверке пар.

2.2.5. Из других алгоритмов вида (4) отметим попытки «улучшения» метода вычетов (6) путем рассмотрения функций вида

или

где — заданное дробное число.

Заметного распространения эти методы не получили.