Комбинированный линейный конгруэнтный генератор - Combined linear congruential generator

А комбинированный линейный конгруэнтный генератор (CLCG) это псевдослучайный генератор чисел алгоритм на основе объединения двух и более линейные конгруэнтные генераторы (LCG). Традиционный LCG имеет период что неадекватно для моделирования сложных систем.^[1] Комбинируя две или более LCG, можно создавать случайные числа с более длительным периодом и лучшими статистическими свойствами.^[1]Алгоритм определяется как:^[2]

${\displaystyle X_{i}\equiv \left(\sum _{j=1}^{k}(-1)^{j-1}Y_{i,j}\right){\pmod {m_{1}-1}}}$

куда:

${\displaystyle m_{1}}$ это "модуль »первого LCG

${\displaystyle Y_{i,j}}$ это я^th вклад от j^th LCG

${\displaystyle X_{i}}$ это я^th сгенерированное случайное целое число

с:

${\displaystyle R_{i}\equiv {\begin{cases}X_{i}/m_{1}&{\text{for }}X_{i}>0\\(m_{1}-1)/m_{1}&{\text{for }}X_{i}=0\end{cases}}}$

куда ${\displaystyle R_{i}}$ это равномерно распределены случайное число от 0 до 1.

Вывод

Если W_я,1, W_я,2, ..., W_{я, k} - любые независимые дискретные случайные величины, одна из которых равномерно распределена от 0 до м₁ - 2, то Z_я равномерно распределяется между 0 и м₁ - 2, где:^[2]

${\displaystyle Z_{i}=\left(\sum _{j=1}^{k}W_{i,j}\right){\pmod {m_{1}-1}}}$

Позволять Икс_я,1, Икс_я,2, ..., Икс_я,k быть выходом из k LCG. Если W_я,j определяется как Икс_я,j - 1, то W_я,j будут примерно равномерно распределены от 0 до м_j − 1.^[2] Коэффициент "(−1)^j−1"неявно выполняет вычитание единицы из Икс_я,j.^[1]

Характеристики

CLCG предоставляет эффективный способ вычисления псевдослучайных чисел. Алгоритм LCG является недорогим в вычислительном отношении.^[3] Результаты нескольких алгоритмов LCG объединяются с помощью алгоритма CLCG для создания псевдослучайных чисел с более длинным период чем достигается с помощью самого метода LCG.^[3]

Период CLCG - это наименьший общий множитель периодов отдельных генераторов, которые на единицу меньше модулей. Поскольку все модули являются нечетными простыми числами, периоды четные и, таким образом, имеют по крайней мере общий делитель 2, но если модули выбраны так, что 2 является наибольший общий делитель каждой пары это приведет к периоду:^[1]

${\displaystyle P={\frac {(m_{1}-1)(m_{2}-1)\cdots (m_{k}-1)}{2^{k-1}}}}$

Пример

Ниже приведен пример алгоритма, предназначенного для использования на 32-разрядных компьютерах:^[2]

${\displaystyle k=2}$

LCG используются со следующими свойствами:

${\displaystyle {\begin{aligned}a_{1}&=40014&a_{2}&=40692\\m_{1}&=2147483563&m_{2}&=2147483399\\c_{1}&=0&c_{2}&=0\end{aligned}}}$

Алгоритм CLCG настроен следующим образом:

1. Посев для первого LCG, ${\displaystyle Y_{0,1}}$, следует выбирать в диапазоне [1, 2147483562].

Семя для второй LCG, ${\displaystyle Y_{0,2}}$, следует выбирать в диапазоне [1, 2147483398].

Набор: ${\displaystyle i=0}$

2. Две LCG оцениваются следующим образом:

${\displaystyle Y_{i+1,1}=40014\times Y_{i,1}{\pmod {2147483563}}}$

${\displaystyle Y_{i+1,2}=40692\times Y_{i,2}{\pmod {2147483399}}}$

3. Уравнение CLCG решается, как показано ниже:

${\displaystyle X_{i+1}=(Y_{i+1,1}-Y_{i+1,2}){\pmod {2147483563}}}$

4. Вычислите случайное число:

${\displaystyle R_{i+1}={\begin{cases}X_{i+1}/2147483563&{\text{for }}X_{i+1}>0\\(X_{i+1}/2147483563)+1&{\text{for }}X_{i+1}<0\\2147483562/2147483563&{\text{for }}X_{i+1}=0\end{cases}}}$

5. Увеличьте счетчик (я = я + 1), затем вернитесь к шагу 2 и повторите.

Максимальный период двух используемых LCG рассчитывается по формуле:^[1]

${\displaystyle (m-1)}$

Это равно 2,1 × 10⁹ для двух используемых LCG.

Этот CLCG, показанный в этом примере, имеет максимальный период:

${\displaystyle (m_{1}-1)(m_{2}-1)/2\approx 2.3\times 10^{18}}$

Это представляет собой огромное улучшение по сравнению с периодом отдельных LCG. Видно, что комбинированный метод увеличивает период на 9 порядков.

Удивительно, но периода этого CLCG может хватить для всех приложений.^[1] Другие алгоритмы, использующие метод CLCG, использовались для создания генераторов псевдослучайных чисел с периодами до 3 × 10⁵⁷.^[4][5][6]

Смотрите также

• Линейный конгруэнтный генератор
• Wichmann – Hill, особый комбинированный LCG, предложенный в 1982 г.

Рекомендации

1. Бэнкс, Джерри; Карсон, Джон С .; Нельсон, Барри Л .; Николь, Дэвид М. (2010). Моделирование дискретных систем (5-е изд.). Прентис Холл. § 7.3.2. ISBN  0-13-606212-1.
2. L'Ecuyer, Пьер (1988). «Эффективные и портативные комбинированные генераторы случайных чисел» (PDF). Коммуникации ACM. 31 (6): 742–749, 774. CiteSeerX  10.1.1.72.88. Дои:10.1145/62959.62969.
3. Панди, Нирадж (6 августа 2008 г.). Реализация функции скачка для линейных конгруэнтных и запаздывающих генераторов Фибоначчи (PDF) (Магистерская диссертация). Государственный университет Флориды. § 2.2. Архивировано из оригинал (PDF) 12 июля 2011 г.. Получено 13 апреля 2012.
4. Л'Экуайер, Пьер (сентябрь – октябрь 1996 г.). «Комбинированные множественные рекурсивные генераторы чисел». Исследование операций. 44 (5): 816–822. Дои:10.1287 / opre.44.5.816.
5. L'Ecuyer, Пьер (январь – февраль 1999 г.). «Хорошие параметры и реализации для комбинированных множественных рекурсивных генераторов случайных чисел». Исследование операций. 47 (1): 159–164. CiteSeerX  10.1.1.48.1341. Дои:10.1287 / opre.47.1.159.
6. Л'Экуайер, Пьер; Р. Симард; E.J. Чен; У. Д. Келтон (ноябрь – декабрь 2002 г.). «Объектно-ориентированный пакет Randon-Number с множеством длинных потоков и подпотоков» (PDF). Исследование операций. 50 (6): 1073–1075. CiteSeerX  10.1.1.25.22. Дои:10.1287 / opre.50.6.1073.358.

внешняя ссылка

• Обзор использования и тестирования генераторов псевдослучайных чисел