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

Инверсный конгруэнтный метод (или генератор Айхенауэра — Лена) — метод генерации псевдослучайных чисел, основанный на использовании обратного по модулю числа для генерации следующего члена последовательности.

Инверсный конгруэнтный метод был предложен Айхенауэром и Леном в 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_{0}=seed}$
${\displaystyle x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n}$	if ${\displaystyle x_{i}\neq 0}$
${\displaystyle x_{i+1}=b}$	if ${\displaystyle x_{i}=0}$

Если число ${\displaystyle X_{n}}$ является составным, элементы последовательности вычисляются следующим образом:

${\displaystyle x_{0}=seed}$
${\displaystyle x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n}$

Параметры подбираются таким образом, чтобы ${\displaystyle (seed,n)=1;(a,n)=1}$.

Последовательность ${\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}$.

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

def ICG(n, a, c, seed):
    if (seed == 0):
        return c
    return (a * modinv(seed, n) + c) % n

seed = 1
n = 5
a = 2
c = 3
count = 10

for i in range(count):
    print(seed)
    seed = ICG(n, a, c, seed)

#include <iostream>
using namespace std;

int mod_inv(int a, int n)
{
	int b0 = n, t, q;
	int x0 = 0, x1 = 1;
	if (n == 1) return 1;
	while (a > 1) 
        {
		q = a / n;
		t = n, n = a % n, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

int ICG(int n, int a, int c, int seed)
{
    if (seed == 0)
      	return c;
    return (a * mod_inv(seed, n) + c) % n;
}

int main(void) 
{
	int seed = 1;
	int n = 5;
	int a = 2;
	int c = 3;
	int count = 10;

	for (int i = 0; i < count; i++)
	{
   		 cout << seed << endl;
         seed = ICG(n, a, c, seed);
	}
	return 0;
}

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

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

Пусть ${\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

Статьи