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

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

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

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

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

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

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

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