Інверсивний конгруентний метод

Інверсивний конгруентний метод (або генератор Ейхенауера - Лена, також можливо Ейченауера - Лехна) - метод генерації псевдовипадкових чисел, заснований на використанні зворотнього по модулю числа для генерації наступного члена послідовності.

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

Опис

Інверсивний конгруентний метод був запропонований Ейченауером і Лехна в 1986 році як заміна лінійному конгруентному методу, що не володіє гратчастою структурою.

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

Основною відмінністю від лінійного методу є використання при генерації послідовності числа зворотнього до попереднього елемента, замість самого попереднього елемента.

Параметрами генератора є:

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

У випадку простого 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}$

У випадку складеного n

Якщо число ${\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)}$ був незвідний.

У разі складеного ${\displaystyle n}$ максимально можливий період дорівнює ${\displaystyle \varphi (n)}$(функція Ейлера).

Приклад

Інверсивний конгруентний генератор з параметрами ${\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}$.

Приклади реалізації

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

Складені інверсивні генератори

Об'єднання двох інверсивних конгруетних генераторів

Основним недоліком інверсивних конгруентних генераторів є зростання складності обчислень при збільшенні періоду. Даний недолік виправлений в складених інверсивних конгруентних генераторах.

Конструкція складених інверсивних генераторів є об'єднанням двох або більше інверсивних конгруентних генераторів.

Нехай ${\displaystyle p_{1},\dots ,p_{r}}$ - різні прості числа, кожне ${\displaystyle p_{j}\geq 5}$. Для кожного індексу ${\displaystyle j}$ в межах ${\displaystyle 1\leq j\ \leq r}$ нехай ${\displaystyle \{x_{n}^{(j)}\}_{n\geq 0}}$ - послідовність елементів ${\displaystyle \in \mathbb {F} _{p_{j}}}$ з періодом ${\displaystyle p_{j}}$. Іншими словами, ${\displaystyle \{x_{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 {x_{n}^{(j)}}{p_{j}}};{n\geq 0};1\leq j\ \leq r}$.

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

Період результуючої послідовності ${\displaystyle T=p_{1}p_{2}\dots p_{r}}$.

Одним з переваг даного підходу є можливість використовувати інверсивні конгруентні генератори працюючі паралельно.

Приклад складеного інверсивного генератора

Нехай ${\displaystyle r=2,p_{1}=5}$ і ${\displaystyle p_{2}=7}$. Для спрощення визначемо ${\displaystyle (x_{k}^{(1)})_{k\geq 0}=(0,1,2,3,4,\dots )}$ і ${\displaystyle (x_{k}^{(2)})_{k\geq 0}=(0,1,2,3,4,5,6,\dots )}$. Для кожного ${\displaystyle 1\leq n\leq 35}$ обчислимо ${\displaystyle x_{n}={\frac {x_{n}^{(1)}}{5}}+{\frac {x_{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\}}$

Переваги інверсивних конгруентних генераторів

Інверсивні конгруентні генератори застосовуються в практичних цілях по ряду причин.

По-перше, інверсивні конгруентні генератори мають досить непогану рівномірність, крім того отримані послідовності абсолютно позбавлені гратчастої структури, характерної для лінійних конгруентних генераторів.

По-друге, числові послідовності, отримані за допомогою ІКГ не мають небажаних статистичних відхилень. Отримані даним методом послідовності перевірені рядом статистичних тестів і залишаються стабільними при зміні параметрів.

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

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

Недоліки інверсивних конгруентних генераторів

Основним недоліком інверсивних конгруентних генераторів є повільна швидкість генерації елементів послідовності: на обчислення одного елементу послідовності витрачається ${\displaystyle O(log(n))}$ операцій множення.

Примітки

1. Кнут, 2013.
2. Hellekalek, 1995, с. 255.
3. Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002, с. 67, 5.3.
4. Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002, с. 69, 5.4.
5. Hellekalek, 1995, с. 256.
6. Eichenauer-Herrmannn, Grothe, Niederreiter et al, 1990, с. 81.
7. Hellekalek, 1995, с. 261.
8. Bubicz, Stoklosa, 2006, с. 2.