Комбинированный линейный конгруэнтный генератор

Комбинированный линейный конгруэнтный генератор ( CLCG ) — это генератора псевдослучайных чисел, алгоритм основанный на объединении двух или более линейных конгруэнтных генераторов (LCG). Традиционный LCG имеет период , которого недостаточно для моделирования сложной системы. ^[1] Объединив два или более LCG, можно создать случайные числа с более длительным периодом и лучшими статистическими свойствами. ^[1]Алгоритм определяется как: ^[2] $X_{i}\equiv \left(\sum _{j=1}^{k}(-1)^{j-1}Y_{i,j}\right){\pmod {m_{1}-1}}$ где:

$m_{1}$ - это « модуль » первого LCG
$Y_{i,j}$ это я ^й вход от j ^й ЛКГ
$X_{i}$ это я ^й сгенерированное случайное целое число

с: $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}}$ где $R_{i}$ — это равномерно распределенное случайное число от 0 до 1.

Вывод

Если Wi _{, ,1} , Wi _{, 2} , ..., Wi _{k распределена} — любые независимые дискретные случайные величины и одна из них равномерно распределена от 0 до m ₁ − 2, то равномерно _{Z i} между 0 и m ₁ − 2, где: ^[2] $Z_{i}=\left(\sum _{j=1}^{k}W_{i,j}\right){\pmod {m_{1}-1}}$

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

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

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

Период CLCG — это наименьшее общее кратное периодов отдельных генераторов, которые на единицу меньше модулей. Поскольку все модули являются нечетными простыми числами, периоды четные и, следовательно, имеют по крайней мере общий делитель 2, но если модули выбраны так, что 2 является наибольшим общим делителем каждой пары, это приведет к периоду: ^[1] $P={\frac {(m_{1}-1)(m_{2}-1)\cdots (m_{k}-1)}{2^{k-1}}}$

Пример

Ниже приведен пример алгоритма, разработанного для использования на 32-разрядных компьютерах: ^[2] $k=2$ LCG используются со следующими свойствами: ${\begin{aligned}a_{1}&=40014&a_{2}&=40692\\m_{1}&=2147483563&m_{2}&=2147483399\\c_{1}&=0&c_{2}&=0\end{aligned}}$

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

Семена для первого LCG, $Y_{0,1}$ , следует выбирать в диапазоне [1, 2147483562].
Семена для второго LCG, $Y_{0,2}$ , следует выбирать в диапазоне [1, 2147483398].
Набор: $i=0$
Два LCG оцениваются следующим образом: $Y_{i+1,1}=40014\times Y_{i,1}{\pmod {2147483563}}$ $Y_{i+1,2}=40692\times Y_{i,2}{\pmod {2147483399}}$
Уравнение CLCG решается, как показано ниже: $X_{i+1}=(Y_{i+1,1}-Y_{i+1,2}){\pmod {2147483563}}$
Вычислите случайное число: $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}}$
Увеличьте счетчик ( i := i + 1), затем вернитесь к шагу 2 и повторите.

Максимальный период двух используемых LCG рассчитывается по формуле: ^[1] $(m-1)$ Это соответствует 2,1×10 ⁹ для двух используемых LCG.

Этот CLCG, показанный в этом примере, имеет максимальный период: $(m_{1}-1)(m_{2}-1)/2\approx 2.3\times 10^{18}$ Это представляет собой огромное улучшение по сравнению с периодом существования отдельных LCG. Видно, что комбинированный метод увеличивает период на 9 порядков.

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

Первый из двух генераторов, использующий b = 40 014 и m = 2 147 483 563, также используется научным калькулятором Texas Instruments TI-30X IIS .

См. также

Линейный конгруэнтный генератор
Вихманн-Хилл , конкретный комбинированный LCG, предложенный в 1982 году.

Ссылки

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

Внешние ссылки

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

[Banks,_Carson,_Nelson,_Nicol-2010-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Бэнкс, Джерри; Карсон, Джон С.; Нельсон, Барри Л.; Никол, Дэвид М. (2010). Моделирование дискретно-событийной системы (5-е изд.). Прентис Холл. § 7.3.2. ISBN 978-0-13-606212-7 .

[L'Ecuyer-1988-2] Jump up to: Перейти обратно: ^а ^б ^с ^д Л'Экуйер, Пьер (1988). «Эффективные и портативные комбинированные генераторы случайных чисел» (PDF) . Коммуникации АКМ . 31 (6): 742–749, 774. CiteSeerX 10.1.1.72.88 . дои : 10.1145/62959.62969 . S2CID 9593394 .

[Pandey-2008-3] Jump up to: Перейти обратно: ^а ^б Пандей, Нирадж (6 августа 2008 г.). Реализация функции скачка вперед для линейных конгруэнтных и запаздывающих генераторов Фибоначчи (PDF) (магистерская диссертация). Государственный университет Флориды. § 2.2. Архивировано из оригинала (PDF) 12 июля 2011 года . Проверено 13 апреля 2012 г.

[L'Ecuyer-1996-4] Л'Экуйер, Пьер (сентябрь – октябрь 1996 г.). «Комбинированные множественные рекурсивные генераторы чисел» . Исследование операций . 44 (5): 816–822. дои : 10.1287/опре.44.5.816 .

[L'Ecuyer-1999-5] Л'Экуйер, Пьер (январь – февраль 1999 г.). «Хорошие параметры и реализации для комбинированных множественных рекурсивных генераторов случайных чисел» . Исследование операций . 47 (1): 159–164. CiteSeerX 10.1.1.48.1341 . дои : 10.1287/опре.47.1.159 .

[L'Ecuyer,_Simard,_Chen,_Kelton-2002-6] Л'Экуйер, Пьер; Р. Симард; Э. Дж. Чен; У. Д. Келтон (ноябрь – декабрь 2002 г.). «Объектно-ориентированный пакет случайных чисел с множеством длинных потоков и подпотоков» (PDF) . Исследование операций . 50 (6): 1073–1075. CiteSeerX 10.1.1.25.22 . дои : 10.1287/опре.50.6.1073.358 .

[1]

[2]

[3]

[4]

[5]

[6]