В сочетании линейного конгруэнтного генератора ( CLCG ) представляет собой псевдослучайные числа генератора алгоритма на основе объединения двух или более линейных конгруэнтные генераторы (LCG). У традиционной LCG период недостаточен для моделирования сложной системы. [1] Комбинируя две или более LCG, можно создавать случайные числа с более длительным периодом и лучшими статистическими свойствами. [1] Алгоритм определяется как: [2]
где:
- " модуль " первого LCG
- это i- й вход из j- го LCG
- это i- е сгенерированное случайное целое число
с участием:
где - равномерно распределенное случайное число от 0 до 1.
Вывод
Если W i , 1 , W i , 2 , ..., W i , k - любые независимые дискретные случайные величины, и одна из них равномерно распределена от 0 до m 1 - 2, то Z i равномерно распределена между 0 и т 1 - 2, где: [2]
Пусть 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]
Пример
Ниже приведен пример алгоритма, предназначенного для использования на 32-разрядных компьютерах: [2]
LCG используются со следующими свойствами:
Алгоритм CLCG настроен следующим образом:
1. Посев для первого LCG, , следует выбирать в диапазоне [1, 2147483562].
- Семя для второй LCG, , следует выбирать в диапазоне [1, 2147483398].
- Набор:
2. Две LCG оцениваются следующим образом:
3. Уравнение CLCG решается, как показано ниже:
4. Вычислите случайное число:
5. Увеличьте счетчик ( i = i + 1), затем вернитесь к шагу 2 и повторите.
Максимальный период двух используемых LCG рассчитывается по формуле :. [1]
Это равняется 2,1 × 10 9 для двух используемых LCG.
Этот CLCG, показанный в этом примере, имеет максимальный период:
Это представляет собой огромное улучшение по сравнению с периодом отдельных LCG. Видно, что комбинированный метод увеличивает период на 9 порядков.
Удивительно, но периода этого CLCG может хватить не для всех приложений. [1] Другие алгоритмы, использующие метод CLCG, использовались для создания генераторов псевдослучайных чисел с периодами до 3 × 10 57 . [4] [5] [6]
Смотрите также
- Линейный конгруэнтный генератор
- Wichmann – Hill , особый комбинированный LCG, предложенный в 1982 г.
Рекомендации
- ^ a b c d e f Бэнкс, Джерри; Карсон, Джон С .; Нельсон, Барри Л .; Николь, Дэвид М. (2010). Моделирование дискретно-событийных систем (5-е изд.). Прентис Холл. § 7.3.2. ISBN 0-13-606212-1.
- ^ а б в г L'Ecuyer, Пьер (1988). «Эффективные и портативные комбинированные генераторы случайных чисел» (PDF) . Коммуникации ACM . 31 (6): 742–749, 774. CiteSeerX 10.1.1.72.88 . DOI : 10.1145 / 62959.62969 .
- ^ а б Панди, Нирадж (6 августа 2008 г.). Реализация функции Leap Ahead для линейных конгруэнтных и запаздывающих генераторов Фибоначчи (PDF) (магистерская диссертация). Государственный университет Флориды. § 2.2. Архивировано из оригинального (PDF) 12 июля 2011 года . Проверено 13 апреля 2012 года .
- ^ L'Ecuyer, Пьер (сентябрь – октябрь 1996 г.). «Комбинированные множественные рекурсивные генераторы чисел» . Исследование операций . 44 (5): 816–822. DOI : 10.1287 / opre.44.5.816 .
- ^ L'Ecuyer, Пьер (январь – февраль 1999 г.). «Хорошие параметры и реализации для комбинированных множественных рекурсивных генераторов случайных чисел» . Исследование операций . 47 (1): 159–164. CiteSeerX 10.1.1.48.1341 . DOI : 10.1287 / opre.47.1.159 .
- ^ Л'Экуайер, Пьер; Р. Симард; EJ Chen; У. Д. Келтон (ноябрь – декабрь 2002 г.). «Объектно-ориентированный пакет Randon-Number с множеством длинных потоков и подпотоков» (PDF) . Исследование операций . 50 (6): 1073–1075. CiteSeerX 10.1.1.25.22 . DOI : 10.1287 / opre.50.6.1073.358 .
Внешние ссылки
- Обзор использования и тестирования генераторов псевдослучайных чисел