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

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

Пример инверсного конгруэнтного генератора с параметрами n = 7, seed = 0, a = 4, c = 5

Описание

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

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

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

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

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

В случае простого n

Значение членов последовательности задается в виде:

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

В случае составного n

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

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

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

Период

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

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

Пример

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

Примеры реализации

Python

Код

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)

C++

Код

#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;
}

Составные инверсные генераторы

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

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

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

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

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

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

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

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

Пример составного инверсного генератора

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

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

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

Преимущества инверсных конгруэнтных генераторов

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

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

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

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

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

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

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

Литература

Книги

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

Статьи

• Eichenauer J., Lehn J. A non-linear congruential pseudo random number generator (англ.) // Statistical Papers — Springer Berlin Heidelberg, Springer Science+Business Media, 1986. — Vol. 27, Iss. 1. — P. 315—326. — ISSN 0932-5026; 1613-9798 — doi:10.1007/BF02932576
• Eichenauer-Herrmann J., Grothe H., Niederreiter H., Topuzoǧlu A. On the lattice structure of a nonlinear generator with modulus 2ᵅ (англ.) // Journal of Computational and Applied Mathematics — Elsevier BV, 1990. — Vol. 31, Iss. 1. — P. 81—85. — ISSN 0377-0427; 1879-1778 — doi:10.1016/0377-0427(90)90338-Z
• Eichenauer-Herrmann J. Inversive congruential pseudorandom numbers avoid the planes (англ.) // Mathematics of Computation — AMS, 1991. — Vol. 56, Iss. 193. — P. 297—301. — ISSN 0025-5718; 1088-6842 — doi:10.2307/2008543
• Eichenauer-Herrmann J., Niederreiter H. Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus (англ.) // Mathematics of Computation — AMS, 1992. — Vol. 58, Iss. 198. — P. 775—779. — ISSN 0025-5718; 1088-6842 — doi:10.2307/2153216
• Eichenauer-Herrmann J. Statistical independence of a new class of inversive congruential pseudorandom numbers (англ.) // Mathematics of Computation — AMS, 1993. — Vol. 60. — P. 375—384. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1993-1159168-9
• Chou W. S. On inversive maximal period polynomials over finite fields (англ.) // Applicable Algebra in Engineering Communication and Computing — Springer Science+Business Media, 1995. — Vol. 6, Iss. 4. — P. 245—250. — ISSN 0938-1279; 1432-0622 — doi:10.1007/BF01235718
• Hellekalek P. Inversive pseudorandom number generators: concepts, results and links (англ.) // WSC'95: Proceedings, 1995 Winter Simulation Conference / D. Goldsman, C. Alexopoulos — Washington, D.C.: IEEE Computer Society, 1995. — P. 255—262. — 1463 p. — ISBN 978-0-7803-3018-4 — doi:10.1145/224401.224612
• Bubicz J., Stoklosa J. Compound Inversive Congruential Generator Design Algorithm (англ.) // IMCSIT 2006: Proceedings of the 4th International Multiconference on Computer Science and Information Technology — Amman: ASPU, 2006. — Vol. 1. — P. 1—6.
• Gille-Genest Anne. Pseudo-Random Numbers Generators. — 2012. (недоступная ссылка)
• Glen Amy. On the Period Length of Pseudorandom Number Sequences // The University of Adelaide: Honours in Pure Mathematics. — 2002.