Алгоритм Л'Экюера, комбинирующий две последовательности

Генератор Парка-Миллера

Хорошее поведение до 10⁸ случайных проб.

Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:

next=a*next % m

при соответствующем выборе констант.

Константы были предложены Park и Miller:

a=7⁵=16807, m=2³¹-1=2147483647

и протестированы в исследованиях Lewis, Goodman, Miller (1969).

Прямое приложение этого метода возможно на языках ассемблера, но языки высокого уровня могут при этом зафиксировать переполнение. Для обхода этого Scharge предложил метод частичной факторизации модуля. Модуль разлагается в выражение:

m=a*q+r

Вычисления идут по следующему алгоритму:

· next = a(next % q) + r[next / q]

· если next <0, то next += m.

В случае использования констант Парка-Миллера можно использовать q=12773 и r=2836.

Алгоритм Л'Экюера, комбинирующий две последовательности

Период генерируемой последовательности практически недостижим: длина оценивается по порядку как 10¹⁸, а для генератора Парка-Миллера это значение не превышало 10 ⁸.

Если требуется число вызовов, превышающее по порядку 10⁸, то для этого случая L'Ecuyer рекомендует комбинировать вывод двух последовательностей с близкими, но отличающимися константами. В его исследованиях хороший результат был получен для значений:

m1=2147483563, a1=40014, q1=53668, r1=12211;

m2=2147483399, a2=40692, q2=52774, r2=3791.

В начале заполняется специальная “тасовочная” таблица коэффициентов (table[]), которая в дальнейшем используется для определения псевдослучайных величин, ее содержимое в процессе генерации чисел изменяется.