Инверсный конгруэнтный метод

Инверсный конгруэнтный метод был предложен Эйченауэром и Лехном в 1986 году[1] как замена линейному конгруэнтному методу, не обладающему решётчатой структурой[2].

Данный метод состоит в вычислении последовательности случайных чисел ${\displaystyle X_{n}}$ в кольце вычетов по модулю натурального числа ${\displaystyle n}$.

Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.

Параметрами генератора являются[3]:

${\displaystyle seed}$ — соль
${\displaystyle a}$ — множитель ${\displaystyle (0\leqslant a<n)}$
${\displaystyle b}$ — приращение ${\displaystyle (0\leqslant b<n)}$

Последовательность ${\displaystyle x_{i+1}}$ периодична, причём период не превышает размерности кольца ${\displaystyle n}$. Максимальный период ${\displaystyle n}$ достигается в случае, если многочлен ${\displaystyle f(x)=x^{2}-bx-a\in \mathbb {F} _{n}[x]}$ является примитивным. Достаточным условием максимального периода последовательности является такой выбор констант ${\displaystyle a}$ и ${\displaystyle b}$, чтобы многочлен ${\displaystyle f(x)}$ был неприводим[4].

В случае составного ${\displaystyle n}$ максимально возможный период равен ${\displaystyle \varphi (n)}$ (функция Эйлера)[5].

Инверсный конгруэнтный генератор с параметрами ${\displaystyle n=5,a=2,b=3,seed=1}$ генерирует последовательность ${\displaystyle \{1,0,3,2,4,1,...\}}$ в кольце ${\displaystyle \mathbb {F} _{5}}$, где числа ${\displaystyle 1}$ и ${\displaystyle 4}$, а также ${\displaystyle 2}$ и ${\displaystyle 3}$ обратны друг другу. В данном примере многочлен ${\displaystyle f(x)=x^{2}-3x-2}$ неприводим в ${\displaystyle \mathbb {F} _{5}[x]}$ и числа ${\displaystyle 0,1,2,3,4}$ не являются его корнями, благодаря чему период максимален и равен ${\displaystyle n=5}$.

Объединение двух инверсных конгруэнтных генераторов

Основным недостатком инверсных конгруэнтных генераторов является возрастание сложности вычислений при увеличении периода. Данный недостаток исправлен в составных инверсных конгруэнтных генераторах.

Конструкция составных инверсных генераторов представляет из себя объединение двух или более инверсных конгруэнтных генераторов.

Пусть ${\displaystyle p_{1},\dots ,p_{r}}$ — различные простые числа, каждое ${\displaystyle p_{j}\geq 5}$. Для каждого индекса ${\displaystyle j}$ в пределах ${\displaystyle 1\leq j\ \leq r}$ пусть ${\displaystyle \{y_{n}^{(j)}\}_{n\geq 0}}$ — последовательность элементов ${\displaystyle \in \mathbb {F} _{p_{j}}}$ с периодом ${\displaystyle p_{j}}$. Другими словами, ${\displaystyle \{y_{n}^{(j)}|0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}}$.

Пусть ${\displaystyle \{x_{n}^{(j)}\}_{n\geq 0}}$ — последовательность случайных чисел в пределах ${\displaystyle x_{n}^{(j)}\in [0;1]}$, где ${\displaystyle x_{n}^{(j)}={\frac {y_{n}^{(j)}}{p_{j}}};{n\geq 0};1\leq j\ \leq r}$.

Результирующая последовательность ${\displaystyle (x_{n})_{n\geq 0}}$ определяется как сумма: ${\displaystyle x_{n}:=x_{n}^{(1)}+x_{n}^{(2)}+\dots +x_{n}^{(r)}\mod 1}$.

Период результирующей последовательности ${\displaystyle T=p_{1}p_{2}\dots p_{r}}$[6].

Одни из преимуществ данного подхода является возможность использовать инверсные конгруэнтные генераторы работающие параллельно.

Пусть ${\displaystyle r=2,p_{1}=5}$ и ${\displaystyle p_{2}=7}$. Для упрощения положим ${\displaystyle (y_{k}^{(1)})_{k\geq 0}=(0,1,2,3,4,\dots )}$ and ${\displaystyle (y_{k}^{(2)})_{k\geq 0}=(0,1,2,3,4,5,6,\dots )}$. Для каждого ${\displaystyle 1\leq n\leq 35}$ вычислим ${\displaystyle x_{n}={\frac {y_{n}^{(1)}}{5}}+{\frac {y_{n}^{(2)}}{7}}}$.

Тогда ${\displaystyle (x_{n})_{n\geq 0}=\{0.0,}$ ${\displaystyle }$${\displaystyle 0.34,}$ ${\displaystyle }$${\displaystyle 0.69,}$ ${\displaystyle }$${\displaystyle 0.03,}$ ${\displaystyle }$${\displaystyle 0.37,}$ ${\displaystyle }$${\displaystyle 0.71,}$ ${\displaystyle }$${\displaystyle 0.06,}$ ${\displaystyle }$${\displaystyle 0.4,}$ ${\displaystyle }$${\displaystyle 0.74,}$ ${\displaystyle }$${\displaystyle 0.09,}$ ${\displaystyle }$${\displaystyle 0.43,}$ ${\displaystyle }$${\displaystyle 0.77,}$ ${\displaystyle }$${\displaystyle 0.11,}$ ${\displaystyle }$${\displaystyle 0.46,}$ ${\displaystyle }$${\displaystyle 0.8,}$ ${\displaystyle }$${\displaystyle 0.14,}$ ${\displaystyle }$${\displaystyle 0.49,}$ ${\displaystyle }$${\displaystyle 0.83,}$ ${\displaystyle }$${\displaystyle 0.17,}$ ${\displaystyle }$${\displaystyle 0.51,}$ ${\displaystyle }$${\displaystyle 0.86,}$ ${\displaystyle }$${\displaystyle 0.2,}$ ${\displaystyle }$${\displaystyle 0.54,}$ ${\displaystyle }$${\displaystyle 0.89,}$ ${\displaystyle }$${\displaystyle 0.23,}$ ${\displaystyle }$${\displaystyle 0.57,}$ ${\displaystyle }$${\displaystyle 0.91,}$ ${\displaystyle }$${\displaystyle 0.26,}$ ${\displaystyle }$${\displaystyle 0.6,}$ ${\displaystyle }$${\displaystyle 0.94,}$ ${\displaystyle }$${\displaystyle 0.29,}$ ${\displaystyle }$${\displaystyle 0.63,}$ ${\displaystyle }$${\displaystyle 0.97,}$ ${\displaystyle }$${\displaystyle 0.31,}$ ${\displaystyle }$${\displaystyle 0.66,}$ ${\displaystyle }$${\displaystyle 0.0\}}$. То есть мы получили последовательность с периодом ${\displaystyle 5\times 7=35}$.

Чтобы избавится от дробных чисел, мы может умножить каждый элемент полученной последовательности на ${\displaystyle 35}$ и получить последовательность целых чисел: ${\displaystyle (x_{n}^{(int)})_{n\geq 0}=\{0,}$ ${\displaystyle 12,}$ ${\displaystyle 24,}$ ${\displaystyle 1,}$ ${\displaystyle 13,}$ ${\displaystyle 25,}$ ${\displaystyle 2,}$ ${\displaystyle 14,}$ ${\displaystyle 26,}$ ${\displaystyle 3,}$ ${\displaystyle 15,}$ ${\displaystyle 26,}$ ${\displaystyle 4,}$ ${\displaystyle 16,}$ ${\displaystyle 28,}$ ${\displaystyle 5,}$ ${\displaystyle 17,}$ ${\displaystyle 28,}$ ${\displaystyle 6,}$ ${\displaystyle 18,}$ ${\displaystyle 30,}$ ${\displaystyle 7,}$ ${\displaystyle 19,}$ ${\displaystyle 31,}$ ${\displaystyle 8,}$ ${\displaystyle 20,}$ ${\displaystyle 32,}$ ${\displaystyle 9,}$ ${\displaystyle 21,}$ ${\displaystyle 33,}$ ${\displaystyle 10,}$ ${\displaystyle 22,}$ ${\displaystyle 34,}$ ${\displaystyle 11,}$ ${\displaystyle 22,}$ ${\displaystyle 0\}}$

Инверсные конгруэнтные генераторы применяются в практических целях по ряду причин.

Во-первых, инверсные конгруэнтные генераторы обладают достаточно неплохой равномерностью[7], кроме того полученные последовательности совершенно лишены решетчатой структуры, характерной для линейных конгруэнтных генераторов[1][8][9].

Во-вторых, двоичные последовательности, полученные с помощью ИКГ не имеют нежелательных статистических отклонений. Полученные данным методом последовательности проверены рядом статистических тестов и остаются стабильными при изменении параметров[7][8][10][11].

В-третьих, составные генераторы обладают теми же свойствами, что и одиночные линейные инверсные генераторы[12], но при этом имеют период значительно превышающий период одиночных генераторов[13]. Кроме того, устройство составных генераторов позволяет добиться высокого прироста производительности при использовании на многопроцессорных системах[14].

Существует алгоритм, позволяющий разрабатывать составные генераторы, обладающие предсказуемыми длиной периода и уровнем сложности, а также хорошими статистическими свойствами выходных последовательностей [15].

Основным недостатком инверсных конгруэнтных генераторов является медленная скорость генерации элементов последовательности: на вычисление одного элемента последовательности затрачивается ${\displaystyle O(log(n))}$ операций умножения[16].

Книги

• Кнут Д. Э. Искусство программирования: Том 2. Получисленные алгоритмы — 3 — М.: Вильямс, 2013. — 828 с. — ISBN 978-5-8459-0081-4

Статьи