Линейные конгруентные генераторы

Сегодня очень часто применяются линейные конгруентные генераторы, созданные Лемером. В них последовательность целых чисел Z₁,Z₂,… определяется по формуле

Z_i=(aZ_i-1+c)( mod m)

Где m – модуль (деление по модулю означает взятие остатка от деления на m), a – множитель, с – приращение и Z₀ – начальное значение являются неотрицательными целыми числами.

Очевидно, что остаток от деления всегда меньше делителя, поэтому . Чтобы получить случайные числа в интервале [0,1), примем U_i=Z_i/m.

Если с=0, то линейный конгруентный генератор называется мультипликативным, а при c>0 – смешанным. Мультипликативные генераторы появились раньше и использовались более интенсивно. Большинство генераторов, которые применяются сегодня, являются мультипликативными. У них не может быть полного периода, однако они более изучены и факт улучшения эффективности в связи с введением смешанных генераторов пока не доказан.

Пусть n – число битов в слове компьютера, которые действительно доступны для хранения данных. Например, если в компьютере используются 32 - битные слова, а крайний левый бит является знаковым то n=31. Модуль стараются выбрать равным m=2ⁿ=2³¹. В этом случае избегают явного деление на m, которое заменяется обработкой ситуации переполнения разрядной сетки.

В качестве параметра a обычно выбирают числа вида 8k+3 или 8k+5. В этом случае для мультипликативного генератора можно получить период 2^n-2, причем операция умножения заменяется сдвигом и сложением (умножение на степень двойки – это, по сути, сдвиг числа в разрядной сетке).

Например, в одном из предлагаемых в литературе генераторов a=1073741821, с=0, m=2³¹, Z₀=65539. Используются 32-разрядные числа, причем первый разряд интерпретируется как знаковый. Полный период такого генератора равен 2^31-2.

Потоки случайных чисел (независимые последовательности) в линейном конгруентном генераторе задаются посредством определения начального числа каждого потока. Например, если нам нужны потоки в 100000 чисел каждый, то зададим для первого потока Z₀ =произвольное значение, для второго потока возьмем начальное значение Z₁₀₀₀₀₀, а для третьего – начальное значение Z₂₀₀₀₀₀ и т.д. Т.е., в качестве потоков выступают непересекающиеся смежные последовательности случайных чисел.

В системе GPSS World используется мультипликативный конгруентный генератор с периодом 2^31-2. Он выдает равномерно распределенные числа в интервале [1, 2 147 483 647], которые затем нормируются и преобразуются в числа из интервала 0 – 0,999999 включительно либо в числа от 0 до 999, в зависимости от контекста использования.

Можно использовать любое количество генераторов без специального их объявления, обращаясь к стандартному числовому атрибуту (системной переменной) RNj. Т.е., RNj – это значение генератора случайных чисел, равномерно распределенных на интервале [0,1). Номер генератора j является одновременно и его начальным значением (Z₀). Таким образом, каждый генератор задает отдельный поток случайных чисел. Изменить начальное значение генератора в процессе его работы можно только для первых 7 генераторов (с номерами 1 ÷ 7) с помощью оператора

RMULT A,B,C,D,E,F,G

Где A, B, …, G - начальные значения генераторов 1, 2, …, 7 соответственно.

Например, RMULT,,111

Генератор номер 3 получает начальное значение 111. (остальные значения не изменяются).

Дата добавления: 2014-01-07