Мультипликативный метод

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

X_i+1 = lX_i + m ( mod M ), (4)

где X_i, l, m, M - неотрицательные целые числа.

Раскрывая (4), получим

X_i = lⁱ X₀ + ( lⁱ - 1) m / ( l - 1 )( mod M ). (5)

Если задано начальное значение X₀, множитель l и аддитивная константа m, то (5) однозначно определяет последовательность целых чисел {X_i}, составленную из остатков от деления на М членов последовательности { lⁱ×X₀ + m ( lⁱ - 1 ) / ( l - 1 )}.

Таким образом, для любого i ³ 1 справедливо неравенство X_i < M. По целым числам последовательности {X_i} можно построить последовательность {х_i} = { Х_i / M } рациональных чисел из единичного интервала (0, 1).

Мультипликативный метод задает последовательность неотрицательных целых чисел { Х_i }, не превосходящих М, по формуле

Х_i+1= l Х_i ( mod M ), (6)

т.е. это частный случай (4) при m = 0.

Для машинной реализации наиболее удобна версия М = p^g, где p - число цифр в системе счисления, принятой в ЭВМ, а g - число бит в машинном слове.

Алгоритм построения последовательности для двоичной машины М = 2^g сводится к выполнению следующих операций:

1) выбрать в качестве Х₀ произвольное нечетное число;

2) вычислить коэффициент l = 8t ± 3, где t - любое целое положительное число;

3) найти произведение lХ₀, содержащее не более 2g значащих разрядов;

4) взять g младших разрядов в качестве первого числа последовательности Х₁, а остальные отбросить;

5) определить дробь х₁ = Х₁ / 2^g из интервала (0, 1);

6) присвоить Х₀ = Х₁;

7) вернуться к пункту 3.

В настоящее время библиотеки стандартных программ ЭВМ для вычисления последовательностей равномерно распределенных случайных чисел основаны на конгруэнтных процедурах. Последовательность, полученная по мультипликативному методу, хорошо удовлетворяет статистическим критериям проверки качества.

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