Инверсный конгруэнтный метод (или генератор Айхенауэра — Лена) — метод генерации псевдослучайных чисел, основанный на использовании обратного по модулю числа для генерации следующего члена последовательности.
Описание Инверсный конгруэнтный метод был предложен Айхенауэром и Леном в 1986 году как замена линейному конгруэнтному методу, не обладающему решётчатой структурой.
Данный метод состоит в вычислении последовательности случайных чисел в кольце вычетов по модулю натурального числа .
Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.
Параметрами генератора являются: — соль — множитель — приращение
В случае простого n Значение членов последовательности задается в виде:
|| if |- | || if
В случае составного n Если число является составным, элементы последовательности вычисляются следующим образом:
Параметры подбираются таким образом, чтобы .
Период Последовательность периодична, причём период не превышает размерности кольца . Максимальный период достигается в случае, если многочлен является примитивным. Достаточным условием максимального периода последовательности является такой выбор констант и , чтобы многочлен был неприводим.
В случае составного максимально возможный период равен (функция Эйлера).
Пример Инверсный конгруэнтный генератор с параметрами генерирует последовательность в кольце , где числа и , а также и обратны друг другу. В данном примере многочлен неприводим в и числа не являются его корнями, благодаря чему период максимален и равен .
Примеры реализации
Python
C++
Составные инверсные генераторы
Основным недостатком инверсных конгруэнтных генераторов является возрастание сложности вычислений при увеличении периода. Данный недостаток исправлен в составных инверсных конгруэнтных генераторах.
Конструкция составных инверсных генераторов представляет из себя объединение двух или более инверсных конгруэнтных генераторов.
Пусть — различные простые числа, каждое . Для каждого индекса в пределах пусть — последовательность элементов с периодом . Другими словами, .
Пусть — последовательность случайных чисел в пределах , где .
Результирующая последовательность определяется как сумма: .
Период результирующей последовательности .
Одни из преимуществ данного подхода является возможность использовать инверсные конгруэнтные генераторы работающие параллельно.
Пример составного инверсного генератора Пусть и . Для упрощения положим and . Для каждого вычислим .
Тогда . То есть мы получили последовательность с периодом .
Чтобы избавиться от дробных чисел, можно умножить каждый элемент полученной последовательности на и получить последовательность целых чисел:
Преимущества инверсных конгруэнтных генераторов Инверсные конгруэнтные генераторы применяются в практических целях по ряду причин.
Во-первых, инверсные конгруэнтные генераторы обладают достаточно неплохой равномерностью, кроме того полученные последовательности совершенно лишены решетчатой структуры, характерной для линейных конгруэнтных генераторов.
Во-вторых, двоичные последовательности, полученные с помощью ИКГ не имеют нежелательных статистических отклонений. Полученные данным методом последовательности проверены рядом статистических тестов и остаются стабильными при изменении параметров.
В-третьих, составные генераторы обладают теми же свойствами, что и одиночные линейные инверсные генераторы, но при этом имеют период значительно превышающий период одиночных генераторов. Кроме того, устройство составных генераторов позволяет добиться высокого прироста производительности при использовании на многопроцессорных системах.
Существует алгоритм, позволяющий разрабатывать составные генераторы, обладающие предсказуемыми длиной периода и уровнем сложности, а также хорошими статистическими свойствами выходных последовательностей .
Недостатки инверсных конгруэнтных генераторов Основным недостатком инверсных конгруэнтных генераторов является медленная скорость генерации элементов последовательности: на вычисление одного элемента последовательности затрачивается операций умножения.
Примечания
Литература Книги
Статьи
Категория:Генераторы псевдослучайных чисел