Линейный конгруэнтный метод
Материал из Википедии — свободной энциклопедии
Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.
Этот алгоритм заключается в итеративном применении следующей формулы:
,
где 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.
Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором констант a и c при заданной разрядности e. Для этих констант выписаны условия, гарантирующие удовлетворительное качество получаемых случайных чисел.
[править] Часто используемые параметры
При реализации выгодно выбирать m = 2e, где e — число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.
Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на m1 / d гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.
В таблице ниже приведены наиболее частно используемые параметры линейных конгруентных генераторов, в частности, в стандартных библиотеках различных компиляторов (функция rand()).
| Source | m | a | c | выдаваемые биты семени в rand() / Random(L) |
|---|---|---|---|---|
| Numerical Recipes | 232 | 1664525 | 1013904223 | |
| Borland C/C++ | 232 | 22695477 | 1 | биты 30..16 в rand(), 30..0 в lrand() |
| GNU Compiler Collection | 232 | 69069 | 5 | биты 30..16 |
| ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++ | 232 | 1103515245 | 12345 | биты 30..16 |
| Borland Delphi, Virtual Pascal | 232 | 134775813 | 1 | биты 63..32 числа (seed * L) |
| Microsoft Visual/Quick C/C++ | 232 | 214013 | 2531011 | биты 30..16 |
| Apple CarbonLib | 231 - 1 | 16807 | 0 | see Park–Miller RNG |
