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

Ця стаття не має інтервікі-посилань. Ви можете допомогти проєкту, знайшовши та додавши їх до відповідного елементу Вікіданих.

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

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

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

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

Параметрами генератора є^[2]:

${\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)}$ був незвідний^[3].

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

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

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

Нехай ${\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\}}$

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

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

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

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

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

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