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

Інверсивний конгруентний метод був запропонований Ейченауером і Лехна в 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_{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}$.

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

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

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

Нехай ${\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))}$ операцій множення.