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

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

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

Опис

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

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

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

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

 — сіль
 — множник
 — приріст

У випадку простого n

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

  if
if

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

Якщо число є складеним, елементи послідовності обчислюються наступним чином:

 

Параметри підбираються таким чинном, щоб .

Період

Послідовність періодична, причому період не перевищує розмірності кільця . Максимальний період досягається в разі, якщо многочлен є примітивним. Достатньою умовою максимального періоду послідовності є такий вибір констант і , щоб многочлен був незвідний[3].

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

Приклад

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

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

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

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

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

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

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

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

Нехай - послідовність випадкових чисел в межах , де .

Результуюча послідовність визначається як сума: .

Період результуючої послідовності [5].

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

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

Нехай і . Для спрощення визначемо і . Для кожного обчислимо .

Тоді . Тобто ми отримаємо послідовність з періодом .

Щоб позбавитися від дробових чисел, помножимо кожен елемент отриманої послідовності на і отримаємо послідовність цілих чисел:

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

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

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

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

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

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

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

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

Примітки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.