Инверсный конгруэнтный метод

Инверсный конгруэнтный метод (или генератор Айхенауэра — Лена) — метод генерации псевдослучайных чисел, основанный на использовании обратного по модулю числа для генерации следующего члена последовательности.

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

Описание

Инверсный конгруэнтный метод был предложен Айхенауэром и Леном в 1986 годуШаблон:Sfn как замена линейному конгруэнтному методу, не обладающему решётчатой структуройШаблон:Sfn.

Данный метод состоит в вычислении последовательности случайных чисел $X_n$ в кольце вычетов по модулю натурального числа $n$.

Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.

Параметрами генератора являютсяШаблон:Sfn:

$seed$ — соль
$a$ — множитель $(0⩽a<n)$
$b$ — приращение $(0⩽b<n)$

В случае простого n

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

$x_0=seed$
$x_{i+1}\equiv (a{x}_i^{-1}+b)modn$	if $x_i\ne 0$
$x_{i+1}=b$	if $x_i=0$

В случае составного n

Если число $X_n$ является составным, элементы последовательности вычисляются следующим образом:

$x_0=seed$
$x_{i+1}\equiv (a{x}_i^{-1}+b)modn$

Параметры подбираются таким образом, чтобы $(seed,n)=1;(a,n)=1$.

Период

Последовательность $x_{i+1}$ периодична, причём период не превышает размерности кольца $n$. Максимальный период $n$ достигается в случае, если многочлен $f(x)=x^2-bx-a\in {𝔽}_n[x]$ является примитивным. Достаточным условием максимального периода последовательности является такой выбор констант $a$ и $b$, чтобы многочлен $f(x)$ был неприводимШаблон:Sfn.Шаблон:Неавторитетный источникШаблон:Нет АИ

В случае составного $n$ максимально возможный период равен $\phi (n)$ (функция Эйлера)Шаблон:Sfn.Шаблон:Неавторитетный источникШаблон:Нет АИ

Пример

Инверсный конгруэнтный генератор с параметрами $n=5,a=2,b=3,seed=1$ генерирует последовательность $\{1,0,3,2,4,1,...\}$ в кольце ${𝔽}_5$, где числа $1$ и $4$, а также $2$ и $3$ обратны друг другу. В данном примере многочлен $f(x)=x^2-3x-2$ неприводим в ${𝔽}_5[x]$ и числа $0,1,2,3,4$ не являются его корнями, благодаря чему период максимален и равен $n=5$.

Составные инверсные генераторы

Объединение двух инверсных конгруэнтных генераторов

Основным недостатком инверсных конгруэнтных генераторов является возрастание сложности вычислений при увеличении периода. Данный недостаток исправлен в составных инверсных конгруэнтных генераторах.

Конструкция составных инверсных генераторов представляет из себя объединение двух или более инверсных конгруэнтных генераторов.

Пусть $p_1,\dots ,p_r$ — различные простые числа, каждое $p_j\ge 5$. Для каждого индекса $j$ в пределах $1\le j\le r$ пусть $\{y_n^{(j)}{\}}_{n\ge 0}$ — последовательность элементов $\in {𝔽}_{p_j}$ с периодом $p_j$. Другими словами, $\{y_n^{(j)}|0\le n\le p_j\}\in {𝔽}_{p_j}$.

Пусть $\{x_n^{(j)}{\}}_{n\ge 0}$ — последовательность случайных чисел в пределах $x_n^{(j)}\in [0;1]$, где $x_n^{(j)}=\frac{y_n^{(j)}}{p_j};n\ge 0;1\le j\le r$.

Результирующая последовательность $(x_n{)}_{n\ge 0}$ определяется как сумма: $x_n:=x_n^{(1)}+x_n^{(2)}+\dots +x_n^{(r)}mod1$.

Период результирующей последовательности $T=p_1{p}_2\dots p_r$Шаблон:Sfn.

Одни из преимуществ данного подхода является возможность использовать инверсные конгруэнтные генераторы работающие параллельно.

Пример составного инверсного генератора

Пусть $r=2,p_1=5$ и $p_2=7$. Для упрощения положим $(y_k^{(1)}{)}_{k\ge 0}=(0,1,2,3,4,\dots )$ and $(y_k^{(2)}{)}_{k\ge 0}=(0,1,2,3,4,5,6,\dots )$. Для каждого $1\le n\le 35$ вычислим $x_n=\frac{y_n^{(1)}}{5}+\frac{y_n^{(2)}}{7}$.

Тогда $(x_n{)}_{n\ge 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\ge 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\}$

Преимущества инверсных конгруэнтных генераторов

Инверсные конгруэнтные генераторы применяются в практических целях по ряду причин.

Во-первых, инверсные конгруэнтные генераторы обладают достаточно неплохой равномерностьюШаблон:Sfn, кроме того полученные последовательности совершенно лишены решетчатой структуры, характерной для линейных конгруэнтных генераторовШаблон:SfnШаблон:SfnШаблон:Sfn.

Во-вторых, двоичные последовательности, полученные с помощью ИКГ не имеют нежелательных статистических отклонений. Полученные данным методом последовательности проверены рядом статистических тестов и остаются стабильными при изменении параметровШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

В-третьих, составные генераторы обладают теми же свойствами, что и одиночные линейные инверсные генераторыШаблон:Sfn, но при этом имеют период значительно превышающий период одиночных генераторовШаблон:Sfn. Кроме того, устройство составных генераторов позволяет добиться высокого прироста производительности при использовании на многопроцессорных системахШаблон:Sfn.

Существует алгоритм, позволяющий разрабатывать составные генераторы, обладающие предсказуемыми длиной периода и уровнем сложности, а также хорошими статистическими свойствами выходных последовательностей Шаблон:Sfn.

Недостатки инверсных конгруэнтных генераторов

Основным недостатком инверсных конгруэнтных генераторов является медленная скорость генерации элементов последовательности: на вычисление одного элемента последовательности затрачивается $O(\log n)$ операций умноженияШаблон:SfnШаблон:Неавторитетный источник.

Литература

Книги

• Шаблон:Source

Статьи