Линейный конгруэнтный метод

Линейный конгруэнтный метод входит в стандартные библиотеки различных компиляторов. Данный метод был предложен американским математиком Дерриком Генри Лемером в 1949 году. Его суть сводится к вычислению последовательности псевдослучайных чисел по одному исходному значению в соответствии с алгоритмом:

,                       (1.40)

где  – функция нахождения остатка от деления. Например:

.

Период получаемой в рамках данного метода псевдослучайной последовательности равен .

Если , то метод называется мультипликативным конгруэнтным, а если  – то смешанным конгруэнтным методом. Наиболее часто применяется смешанный конгруэнтный метод.

При выборе числа  необходимо учитывать, что оно должно быть довольно большим. На практике при реализации данного метода чаще всего выбирают , где – число битов в машинном слове. Выбор множителя и приращения  в основном обусловлен необходимостью достижения периода максимальной длины.

Ниже в таблице 1.1 приведены числовые параметры некоторые из известных алгоритмов, применяемых в различных компиляторах и библиотеках.

Таблица 1.1

Примеры числовых значений параметров ,  и

Применение
Borland C/C++		22695477	1
Borland Delphi, Virtual Pascal		134775813	1
Microsoft Visual Basic		1140671485	12820163
Java		25214903917	11

Одной из рекомендаций при выборе числовых значений данных параметров состоит в следующем:

, , ,            (1.41)

причем остаток от деления  на 8 должен составлять 3 или 5 (то есть или ), а число  должно быть целым нечетным.