12-10-2023
Инверсный конгруэнтный метод — метод генерации псевдослучайных чисел, основанный на использовании обратного по модулю числа для генерации следующего члена последовательности.
Инверсный конгруэнтный метод был предложен Эйченауэром и Лехном в 1986 году[1], как замена линейному конгруэнтному методу не обладающая решетчатой структурой[2].
Данный метод состоит в вычислении последовательности случайных чисел в кольце вычетов по модулю натурального числа .
Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.
Параметрами генератора являются[3]:
| — соль | |
| — множитель | |
| — приращение |
Значение членов последовательности задается в виде:
| if | |
| if |
Если число является составным, элементы последовательности вычисляются следующим образом:
Параметры подбираются таким образом, чтобы .
Последовательность периодична, причём период не превышает размерности кольца . Максимальный период достигается в случае, если многочлен является примитивным. Достаточным условием максимального периода последовательности является такой выбор констант и , чтобы многочлен был неприводим[4].[неавторитетный источник? 32 дня]
В случае составного максимально возможный период равен (функция Эйлера)[5].[неавторитетный источник? 32 дня]
Инверсный конгруэнтный генератор с параметрами генерирует последовательность в кольце , где числа и , а также и обратны друг другу. В данном примере многочлен неприводим в и числа не являются его корнями, благодаря чему период максимален и равен .
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;
}
Основным недостатком инверсных конгруэнтных генераторов является возрастание сложности вычислений при увеличении периода. Данный недостаток исправлен в составных инверсных конгруэнтных генераторах.
Конструкция составных инверсных генераторов представляет из себя объединение двух или более инверсных конгруэнтных генераторов.
Пусть - различные простые числа, каждое . Для каждого индекса в пределах пусть — последовательность элементов с периодом . Другими словами, .
Пусть — последовательность случайных чисел в пределах , где .
Результирующая последовательность определяется как сумма: .
Период результирующей последовательности [6].
Одни из преимуществ данного подхода является возможность использовать инверсные конгруэнтные генераторы работающие параллельно.
Пусть и . Для упрощения положим and . Для каждого вычислим .
Тогда . То есть мы получили последовательность с периодом .
Чтобы избавится от дробных чисел, мы может умножить каждый элемент полученной последовательности на и получить последовательность целых чисел:
Инверсные конгруэнтные генераторы применяются в практических целях по ряду причин.
Во-первых, инверсные конгруэнтные генераторы обладают достаточно неплохой равномерностью[7], кроме того полученные последовательности совершенно лишены решетчатой структуры, характерной для линейных конгруэнтных генераторов[1][8][9].
Во-вторых, двоичные последовательности, полученные с помощью ИКГ не имеют нежелательных статистических отклонений. Полученные данным методом последовательности проверены рядом статистических тестов и остаются стабильными при изменении параметров[7][8][10][11].
В-третьих, составные генераторы обладают теми же свойствами, что и одиночные линейные инверсные генераторы[12], но при этом имеют период значительно превышающий период одиночных генераторов[13]. Кроме того, устройство составных генераторов позволяет добиться высокого прироста производительности при использовании на многопроцессорных системах[14].
Существует алгоритм, позволяющий разрабатывать составные генераторы, обладающие предсказуемыми длиной периода и уровнем сложности, а также хорошими статистическими свойствами выходных последовательностей [15].
Основным недостатком инверсных конгруэнтных генераторов является медленная скорость генерации элементов последовательности: на вычисление одного элемента последовательности затрачивается операций умножения[16].[неавторитетный источник? 32 дня]
