Линейный конгруэнтный метод
Материал из Википедии — свободной энциклопедии
Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографическтой стойкостью. Используется в качестве стандартного генератора многими компиляторами.
Этот алгоритм заключается в итеративном применении следующей формулы:
,
где a > 0, c > 0, m > 0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности Xj определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:
- НОД (c, m) = 1 (то есть c и m взаимно просты);
- a - 1 кратно p для всех простых p — делителей m;
- a - 1 кратно 4, если m кратно 4.
При реализации выгодно выбирать m = 2e, где e — число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.
Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на m1 / d гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.
Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором констант a и c при заданной разрядности e. Для этих констант выписаны условия, гарантирующие удовлетворительное качество получаемых случайных чисел. Numerical Recipes in C рекомендует следующие значения: a = 1664525, c = 1013904223, m = 232
