Русская Википедия:Инверсный конгруэнтный метод
Инверсный конгруэнтный метод (или генератор Айхенауэра — Лена) — метод генерации псевдослучайных чисел, основанный на использовании обратного по модулю числа для генерации следующего члена последовательности.
Описание
Инверсный конгруэнтный метод был предложен Айхенауэром и Леном в 1986 годуШаблон:Sfn как замена линейному конгруэнтному методу, не обладающему решётчатой структуройШаблон:Sfn.
Данный метод состоит в вычислении последовательности случайных чисел <math>X_{n}</math> в кольце вычетов по модулю натурального числа <math>n</math>.
Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.
Параметрами генератора являютсяШаблон:Sfn:
| <math>seed</math> — соль | |
| <math>a</math> — множитель <math>(0 \leqslant a < n)</math> | |
| <math>b</math> — приращение <math>(0 \leqslant b < n)</math> |
В случае простого n
Значение членов последовательности задается в виде:
<math> x_0 = seed </math> <math> x_{i+1} \equiv (ax_i^{-1} + b) \mod n </math> if <math>x_i\ne 0</math> <math> x_{i+1} = b </math> if <math>x_i=0</math>
В случае составного n
Если число <math>X_{n}</math> является составным, элементы последовательности вычисляются следующим образом:
<math> x_0 = seed </math> <math> x_{i+1} \equiv (ax_i^{-1} + b) \mod n </math>
Параметры подбираются таким образом, чтобы <math>(seed, n)=1; (a,n)=1</math>.
Период
Последовательность <math> x_{i+1} </math> периодична, причём период не превышает размерности кольца <math>n</math>. Максимальный период <math>n</math> достигается в случае, если многочлен <math>f(x)=x^2-bx-a \in \mathbb{F}_n[x]</math> является примитивным. Достаточным условием максимального периода последовательности является такой выбор констант <math>a</math> и <math>b</math>, чтобы многочлен <math>f(x)</math> был неприводимШаблон:Sfn.Шаблон:Неавторитетный источникШаблон:Нет АИ
В случае составного <math>n</math> максимально возможный период равен <math>\varphi(n)</math> (функция Эйлера)Шаблон:Sfn.Шаблон:Неавторитетный источникШаблон:Нет АИ
Пример
Инверсный конгруэнтный генератор с параметрами <math> n = 5 , a = 2 , b = 3 , seed = 1</math> генерирует последовательность <math>\{1,0,3,2,4,1,...\}</math> в кольце <math>\mathbb F_5 </math>, где числа <math>1</math> и <math>4</math>, а также <math>2</math> и <math>3</math> обратны друг другу. В данном примере многочлен <math>f(x)=x^2-3x-2</math> неприводим в <math>\mathbb F_5[x]</math> и числа <math>0,1,2,3,4</math> не являются его корнями, благодаря чему период максимален и равен <math> n = 5 </math>.
Примеры реализации
Python
C++
Составные инверсные генераторы
Основным недостатком инверсных конгруэнтных генераторов является возрастание сложности вычислений при увеличении периода. Данный недостаток исправлен в составных инверсных конгруэнтных генераторах.
Конструкция составных инверсных генераторов представляет из себя объединение двух или более инверсных конгруэнтных генераторов.
Пусть <math>p_1,\dots , p_r</math> — различные простые числа, каждое <math>p_j\geq 5</math>. Для каждого индекса <math>j</math> в пределах <math>1 \leq j \ \leq r</math> пусть <math>\{y_n^{(j)}\}_{n\geq 0}</math> — последовательность элементов <math>\in \mathbb F_{p_j} </math> с периодом <math>p_j</math>. Другими словами, <math>\{y_n^{(j)} | 0\leq n \leq p_j\} \in \mathbb F_{p_j} </math>.
Пусть <math>\{x_n^{(j)}\}_{n\geq 0}</math> — последовательность случайных чисел в пределах <math>x_n^{(j)} \in [0;1] </math>, где <math>x_n^{(j)} = \frac{y_n^{(j)}}{p_j} ; {n\geq 0} ; 1 \leq j \ \leq r</math>.
Результирующая последовательность <math>(x_n)_{n\geq 0}</math> определяется как сумма: <math>x_n:=x_n^{(1)}+x_n^{(2)}+\dots +x_n^{(r)} \mod 1</math>.
Период результирующей последовательности <math> T = p_1 p_2 \dots p_r</math>Шаблон:Sfn.
Одни из преимуществ данного подхода является возможность использовать инверсные конгруэнтные генераторы работающие параллельно.
Пример составного инверсного генератора
Пусть <math>r =2, p_1=5</math> и <math>p_2 =7</math>. Для упрощения положим <math>(y_k^{(1)})_{k\geq 0} = (0,1,2,3,4,\dots)</math> and <math>(y_k^{(2)})_{k\geq 0} =(0,1,2,3,4,5,6,\dots)</math>. Для каждого <math>1 \leq n \leq 35 </math> вычислим <math>x_n=\frac{y_n^{(1)}}{5}+\frac{y_n^{(2)}}{7}</math>.
Тогда <math>(x_n)_{n\geq 0}=\{0.0 , </math> <math> </math><math> 0.34 , </math> <math> </math><math> 0.69 , </math> <math> </math><math> 0.03 , </math> <math> </math><math> 0.37 , </math> <math> </math><math> 0.71 , </math> <math> </math><math> 0.06 , </math> <math> </math><math> 0.4 , </math> <math> </math><math> 0.74 , </math> <math> </math><math> 0.09 , </math> <math> </math><math> 0.43 , </math> <math> </math><math> 0.77 , </math> <math> </math><math> 0.11 , </math> <math> </math><math> 0.46 , </math> <math> </math><math> 0.8 , </math> <math> </math><math> 0.14 , </math> <math> </math><math> 0.49 , </math> <math> </math><math> 0.83 , </math> <math> </math><math> 0.17 , </math> <math> </math><math> 0.51 , </math> <math> </math><math> 0.86 , </math> <math> </math><math> 0.2 , </math> <math> </math><math> 0.54 , </math> <math> </math><math> 0.89 , </math> <math> </math><math> 0.23 , </math> <math> </math><math> 0.57 , </math> <math> </math><math> 0.91 , </math> <math> </math><math> 0.26 , </math> <math> </math><math> 0.6 , </math> <math> </math><math> 0.94 , </math> <math> </math><math> 0.29 , </math> <math> </math><math> 0.63 , </math> <math> </math><math> 0.97 , </math> <math> </math><math> 0.31 , </math> <math> </math><math> 0.66 , </math> <math> </math><math> 0.0\}</math>. То есть мы получили последовательность с периодом <math>5 \times 7 = 35</math>.
Чтобы избавится от дробных чисел, можно умножить каждый элемент полученной последовательности на <math>35</math> и получить последовательность целых чисел: <math>(x_n^{(int)})_{n\geq 0}=\{0 , </math> <math> 12 , </math> <math> 24 , </math> <math> 1 , </math> <math> 13 , </math> <math> 25 , </math> <math> 2 , </math> <math> 14 , </math> <math> 26 , </math> <math> 3 , </math> <math> 15 , </math> <math> 26 , </math> <math> 4 , </math> <math> 16 , </math> <math> 28 , </math> <math> 5 , </math> <math> 17 , </math> <math> 28 , </math> <math> 6 , </math> <math> 18 , </math> <math> 30 , </math> <math> 7 , </math> <math> 19 , </math> <math> 31 , </math> <math> 8 , </math> <math> 20 , </math> <math> 32 , </math> <math> 9 , </math> <math> 21 , </math> <math> 33 , </math> <math> 10 , </math> <math> 22 , </math> <math> 34 , </math> <math> 11 , </math> <math> 22 , </math> <math> 0\}</math>
Преимущества инверсных конгруэнтных генераторов
Инверсные конгруэнтные генераторы применяются в практических целях по ряду причин.
Во-первых, инверсные конгруэнтные генераторы обладают достаточно неплохой равномерностьюШаблон:Sfn, кроме того полученные последовательности совершенно лишены решетчатой структуры, характерной для линейных конгруэнтных генераторовШаблон:SfnШаблон:SfnШаблон:Sfn.
Во-вторых, двоичные последовательности, полученные с помощью ИКГ не имеют нежелательных статистических отклонений. Полученные данным методом последовательности проверены рядом статистических тестов и остаются стабильными при изменении параметровШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
В-третьих, составные генераторы обладают теми же свойствами, что и одиночные линейные инверсные генераторыШаблон:Sfn, но при этом имеют период значительно превышающий период одиночных генераторовШаблон:Sfn. Кроме того, устройство составных генераторов позволяет добиться высокого прироста производительности при использовании на многопроцессорных системахШаблон:Sfn.
Существует алгоритм, позволяющий разрабатывать составные генераторы, обладающие предсказуемыми длиной периода и уровнем сложности, а также хорошими статистическими свойствами выходных последовательностей Шаблон:Sfn.
Недостатки инверсных конгруэнтных генераторов
Основным недостатком инверсных конгруэнтных генераторов является медленная скорость генерации элементов последовательности: на вычисление одного элемента последовательности затрачивается <math>O(\log n)</math> операций умноженияШаблон:SfnШаблон:Неавторитетный источник.
Примечания
Литература
- Книги
- Статьи
