Линейный конгруэнтный генератор: формула и период

Линейный конгруэнтный генератор (ЛКГ) - это простейший алгоритм получения псевдослучайных чисел, который задаётся всего одной рекуррентной формулой и при этом лежит в основе генераторов стандартных библиотек языков C, Java и Pascal. Разобраться, как он работает, нужно каждому, кто изучает теорию вероятностей, дискретную математику или пишет собственные алгоритмы тестирования. Покрути параметры в калькуляторе ниже - он сразу покажет последовательность и диаграмму рассеяния, а потом мы разберём каждую формулу строго.

Формула линейного конгруэнтного генератора

В основе ЛКГ лежит одна рекуррентная формула:

$X_{n+1} = (a \cdot X_n + c) \bmod m,$

где $a$ - множитель (мультипликативная константа), $c$ - приращение (инкремент), $m$ - модуль, $X_0$ - начальное значение, называемое зерном или «seed». Каждый следующий элемент порождается из предыдущего умножением на $a$, прибавлением $c$ и взятием остатка от деления на $m$. Все числа последовательности лежат в диапазоне от $0$ до $m - 1$.

Если $c = 0$, генератор называют мультипликативным конгруэнтным генератором (МКГ); если $c \neq 0$ - смешанным или полным ЛКГ. Мультипликативный вариант не может породить $0$ (иначе вся последовательность заглохнет), а смешанный допускает любое начальное зерно.

Рассчитать для своей задачи

Период генератора и теорема Халла-Добелла

Главная характеристика ЛКГ - длина периода $T$: через $T$ шагов последовательность начнёт повторяться. Максимально возможный период равен $m$. Наивный выбор $a$ и $c$ легко даёт маленький период - например, при $a=2, c=0, m=16, X_0=1$ последовательность имеет период всего $1$ (зациклится на $0$ через несколько шагов).

Теорема Халла-Добелла (Hull-Dobell, 1962) полностью описывает, когда смешанный ЛКГ достигает периода $m$:

$T = m \iff \begin{cases} \gcd(c, m) = 1, \\ a \equiv 1 \pmod{p} \text{ для каждого простого } p \mid m, \\ a \equiv 1 \pmod{4} \text{ если } 4 \mid m. \end{cases}$

Другими словами: $c$ должно быть взаимно простым с $m$; множитель $a - 1$ должен делиться на все простые делители $m$; а если $m$ делится на $4$, то и $a - 1$ обязан делиться на $4$. Если хотя бы одно из условий нарушено, период окажется строго меньше $m$.

Рассчитать для своей задачи

На диаграмме рассеяния пары $(X_n, X_{n+1})$ всегда ложатся на конечное число параллельных прямых - это не дефект реализации, а фундаментальное свойство линейных конгруэнтных генераторов, доказанное в теореме Марсальи (1968). Число прямых равно $\sqrt[2]{m}$ в двумерном случае и убывает в высших размерностях.

Спектральный тест и качество генератора

Диаграмма рассеяния - простейший визуальный тест качества. Более строгий инструмент - спектральный тест: он измеряет расстояние между соседними параллельными гиперплоскостями в $k$-мерном пространстве, на которые укладываются наборы $(X_n, X_{n+1}, \ldots, X_{n+k-1})$. Чем больше это расстояние, тем хуже генератор: он порождает числа, которые имеют заметную решёточную структуру, а не распределены равномерно.

Для классического генератора стандарта ANSI C ($a = 1\,103\,515\,245$, $c = 12\,345$, $m = 2^{32}$) спектральный тест выявляет плохую трёхмерную структуру - тройки чисел ложатся всего на 15 плоскостей. Именно поэтому современные стандарты вроде PCG или xorshift заменили ЛКГ более сложными конструкциями, хотя и надстроенными поверх той же базовой идеи.

Стандартные параметры в языках программирования

ЛКГ был основным PRNG в системных библиотеках на протяжении десятилетий:

Обратите внимание: почти везде $m$ - степень двойки. Это удобно для реализации на двоичных ЭВМ: операция mod 2^k выполняется через побитовое И (& (m-1)), то есть без деления. Младшие биты выходной последовательности при степени двойки в модуле имеют значительно меньший период: бит $k$ имеет период $2^{k+1}$. Из-за этого в коде rand() % 2 (чётность) ANSI C даёт чередование 0,1,0,1,... - это не случайность, это закономерное следствие структуры генератора.

Пример вычисления вручную

Рассмотрим учебный пример: $a = 5$, $c = 3$, $m = 16$, $X_0 = 0$.

$X_1 = (5 \cdot 0 + 3) \bmod 16 = 3,$ $X_2 = (5 \cdot 3 + 3) \bmod 16 = 18 \bmod 16 = 2,$ $X_3 = (5 \cdot 2 + 3) \bmod 16 = 13,$ $X_4 = (5 \cdot 13 + 3) \bmod 16 = 68 \bmod 16 = 4.$

Продолжая, получаем последовательность: $0, 3, 2, 13, 4, 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9$, а затем снова $0$. Период равен $16 = m$. Проверим условия Халла-Добелла: $\gcd(3, 16) = 1$ (выполнено); $m = 16 = 2^4$, единственный простой делитель - $2$, $a - 1 = 4$ делится на $2$ (выполнено) и на $4$ (выполнено). Все три условия в силе - отсюда и полный период.

Частые ошибки

• Подстановка $c = 0$ без проверки периода. Мультипликативный ЛКГ ($c = 0$) не имеет периода $m$ ни при каких $a$ и $m = 2^k$: нулевое зерно даёт постоянную нулевую последовательность, а ненулевые зёрна дают период не более $m/4$. Для степеней двойки мультипликативный генератор работает только если зерно нечётно.
• Перемешивание знаков при операции mod. В C и C++ оператор % для отрицательных чисел даёт отрицательный остаток. Если промежуточное значение $a \cdot X_n + c$ переполняет int, результат непредсказуем. Используй unsigned long или явный ((a * x + c) % m + m) % m.
• Использование младших битов. При $m = 2^k$ младший бит меняется с периодом $2$, следующие с периодом $4$ и т.д. Для отбора случайного числа из $[0, N)$ всегда берите старшие биты: (lcg() >> 16) % N, а не lcg() % N.
• Зависимость последовательности от зерна. Зерно полностью определяет всю последовательность. Если программа использует одно и то же начальное значение (например, $X_0 = 1$ жёстко прошито), «случайные» числа одинаковы в каждом запуске.
• Ожидание криптостойкости. ЛКГ - не криптографический PRNG. Зная $k$ последовательных выходов, можно восстановить $a$, $c$ и $m$ с помощью алгоритма, работающего за полиномиальное время. Для нужд криптографии применяют CSPRNG.

FAQ

Как выбрать параметры ЛКГ для максимального периода? Используй теорему Халла-Добелла: $\gcd(c, m) = 1$; $a - 1$ делится на все простые множители $m$; если $4 \mid m$, то $4 \mid a - 1$. При $m = 2^{32}$ хороший выбор: $a = 1\,664\,525$, $c = 1\,013\,904\,223$ (параметры Numerical Recipes). Проверить период легко в калькуляторе выше - выбери пресет или введи собственные значения.

Чем ЛКГ отличается от вихря Мерсенна? Вихрь Мерсенна (Mersenne Twister) имеет период $2^{19937} - 1$ против $m \le 2^{64}$ у типичного ЛКГ. MT проходит спектральный тест в 623 измерениях, тогда как ЛКГ рассыпается уже в 3-10 измерениях. При этом ЛКГ занимает в памяти всего одно число состояния и исполняется за 2-3 операции, а MT требует 625 слов состояния.

Почему диаграмма рассеяния ЛКГ показывает прямые линии? Это прямое следствие линейности формулы: $X_{n+1} = a \cdot X_n + c \pmod{m}$. Каждое значение $X_{n+1}$ линейно зависит от $X_n$, поэтому пара $(X_n, X_{n+1})$ лежит на прямой $y = ax + c$ в кольце $\mathbb{Z}_m$. При конечном $m$ прямая «заворачивается» и распадается на несколько параллельных отрезков. Число таких линий - мера качества генератора в спектральном тесте.

Коротко

Линейный конгруэнтный генератор порождает последовательность псевдослучайных чисел по формуле $X_{n+1} = (a \cdot X_n + c) \bmod m$. Максимальный период $m$ достигается тогда и только тогда, когда выполнены условия теоремы Халла-Добелла: $c$ взаимно просто с $m$, а $a - 1$ делится на все простые делители $m$ (и дополнительно на 4, если $4 \mid m$). Главный недостаток ЛКГ - гиперплоскостная структура, видимая на диаграмме рассеяния и разрушающая многомерную равномерность. Тем не менее ЛКГ остаётся стандартом во многих учебных и системных реализациях из-за предельной простоты и высокой скорости.