Список генераторов случайных чисел - List of random number generators

Генераторы случайных чисел важны во многих технических приложениях, включая физика, инженерное дело или же математический компьютерные исследования (например, Монте-Карло моделирование), криптография и играть в азартные игры (на игровые серверы ).

В этот список входит множество распространенных типов, независимо от качества.

Генераторы псевдослучайных чисел (ГПСЧ)

При использовании генератор псевдослучайных чисел, иметь ввиду Джон фон Нейман изречение «Всякий, кто рассматривает арифметические методы получения случайных чисел, конечно, находится в состоянии греха».[1]

Следующие алгоритмы являются генераторами псевдослучайных чисел.

ГенераторДатаПервые сторонникиРекомендацииПримечания
Метод средних квадратов1946Дж. Фон Нейман[2]В первоначальном виде он низкого качества и представляет только исторический интерес.
Генератор Лемера1951Д. Х. Лемер[3]Один из самых ранних и влиятельных дизайнов.
Линейный конгруэнтный генератор (LCG)1958У. Э. Томсон; А. Ротенберг[4][5]Обобщение генератора Лемера и исторически наиболее влиятельный и изученный генератор.
Генератор Фибоначчи с запаздыванием (LFG)1958Дж. Дж. Митчелл и Д. П. Мур[6]
Регистр сдвига с линейной обратной связью (LFSR)1965Р. К. Таусворте[7]Очень влиятельный дизайн. Также называется генераторами Tausworthe.
Генератор Вихмана – Хилла1982Б. А. Вихманн, Д. И. Хилл[8]Комбинация из трех небольших LCG, подходящих для 16-битные процессоры. Широко используется во многих программах, например он используется в Excel 2003 и более поздние версии для функции RAND[9] и он был генератором по умолчанию на языке Python до версии 2.2.[10]
Правило 301983С. Вольфрам[11]На основе клеточных автоматов.
Инверсивный конгруэнтный генератор (ICG)1986Дж. Эйхенауэр и Дж. Лен[12]
Генератор Парка-Миллера1988С. К. Парк и К. В. Миллер[13]Конкретная реализация генератора Лемера, широко используемого, поскольку встроена в C и C ++ языках как функция `minstd '.
Генератор желудя(обнаружен в 1984 г.) 1989 г.Р. С. Викрамаратна[14] [15]В Аdditive Congruential рAndom Nгенератор умбры.

Просто реализовать, быстро, но малоизвестно. При соответствующей инициализации проходит все текущие эмпирические наборы тестов и формально доказывает сходимость. Легко продлить на произвольную длину периода и улучшить статистические характеристики для более высоких измерений и с более высокой точностью.

Генератор MIXMAX1991Г. К. Саввиди, Н. Г. Тер-Арутюнян-Саввиди[16]Он является членом класса матричных линейных конгруэнтных генераторов, обобщения LCG. Обоснование семейства генераторов MIXMAX опирается на результаты эргодической теории и классической механики.
Надстройка с переносом (AWC)1991Г. Марсалья, А. Заман[17]Модификация генераторов Фибоначчи с запаздыванием.
Вычесть с займом (SWB)1991Г. Марсалья, А. Заман[17]Модификация генераторов Фибоначчи с запаздыванием. Генератор SWB является основой для генератора RANLUX,[18] широко используется, например для моделирования физики элементарных частиц.
Максимально периодические обратные1992Р. А. Дж. Мэтьюз[19]Метод, уходящий корнями в теорию чисел, но никогда не применяемый на практике.
ЦЕЛОВАТЬ1993Г. Марсалья[20]Прототипный пример генератора комбинаций.
Умножение с переносом (MWC)1994Г. Марсалья; К. Коч[21][22]
Дополнительное умножение с переносом (CMWC)1997Р. Кутюр и П. Л'Экуайер[23]
Мерсенн Твистер (MT)1998М. Мацумото и Т. Нисимура[24]Тесно связан с LFSR. В его реализации MT19937, вероятно, наиболее часто используется современный ГПСЧ. Генератор по умолчанию в р и Язык Python начиная с версии 2.3.
Xorshift2003Г. Марсалья[25]Это очень быстрый подтип генераторов LFSR. Марсалья также предложил в качестве улучшения генератор xorwow, в котором выходной сигнал генератора xorshift добавлен с помощью Последовательность Вейля. Генератор xorwow является генератором по умолчанию в библиотеке CURAND nVidia. CUDA интерфейс прикладного программирования для графических процессоров.
Хорошо равнораспределенный длиннопериодный линейный (ЧТО Ж)2006Ф. Паннетон, П. Л'Экуайер и М. Мацумото[26]LFSR тесно связан с Mersenne Twister, стремясь исправить некоторые из его недостатков.
Небольшой некриптографический ГПСЧ (JSF)2007Боб Дженкинс[27]
Расширенная система рандомизации (ARS)2011Дж. Сэлмон, М. Мораес, Р. Дрор и Д. Шоу[28]Упрощенная версия Блочный шифр AES, что приводит к очень высокой производительности системы, поддерживающей AES-NI.
Threefry2011Дж. Сэлмон, М. Мораес, Р. Дрор и Д. Шоу[28]Упрощенная версия блочного шифра Threefish, подходящая для реализации на GPU.
Филокс2011Дж. Сэлмон, М. Мораес, Р. Дрор и Д. Шоу[28]Упрощение и модификация блочного шифра Три рыбы с добавлением S-коробка.
SplitMix2014Г. Л. Стил, Д. Ли и К. Х. Флад[29]На основе функции финального микширования MurmurHash3. Входит в Java Development Kit 8 и выше.
Конгруэнтный генератор с перестановками (PCG)2014М. Э. О'Нил[30]Модификация LCG.
Генератор битов случайного цикла (RCB)2016Р. Кукман[31]RCB описывается как генератор битовых последовательностей, созданный для преодоления некоторых недостатков Mersenne Twister и ограничения коротких периодов / битовой длины генераторов сдвига / модуля.
Последовательность Вейля в среднем квадрате ГПСЧ2017Б. Видынски[32]Вариант на Джон фон Нейман оригинальный метод среднего квадрата, этот генератор может быть самым быстрым ГПСЧ, прошедшим все статистические тесты.
Xoroshiro128 +2018Д. Блэкман, С. Винья[33]Модификация генераторов Marsaglia Xorshift, одного из самых быстрых генераторов на современном 64-битный ЦП. Связанные генераторы включают xoroshiro128 **, xoshiro256 + и xoshiro256 **.
64-битный MELG2018С. Харасе, Т. Кимото[34]Реализация 64-битный максимально равнораспределенный F2-линейные образующие с простым периодом Мерсенна.
Квадраты ГСЧ2020Б. Видынски[35]А счетчик версия Последовательность Вейля в среднем квадрате ГПСЧ. По словам автора, это один из самых быстрых счетчик генераторы.

Криптографические алгоритмы

Шифр алгоритмы и криптографические хеши могут использоваться как очень качественные генераторы псевдослучайных чисел. Однако, как правило, они значительно медленнее (обычно в 2–10 раз), чем быстрые некриптографические генераторы случайных чисел.

К ним относятся:

Несколько криптографически безопасных генераторов псевдослучайных чисел не полагаются на алгоритмы шифрования, а пытаются математически связать сложность отличия их вывода от "истинного" случайного потока с вычислительно сложной задачей. Эти подходы теоретически важны, но слишком медленны, чтобы их можно было использовать в большинстве приложений. Они включают:

Генераторы случайных чисел, использующие внешнюю энтропию

Эти подходы сочетают в себе генератор псевдослучайных чисел (часто в форме блочного или потокового шифра) с внешним источником случайности (например, движениями мыши, задержкой между нажатиями на клавиатуру и т. Д.).

Серверы случайных чисел

Следующий (не исчерпывающий) список веб-сайтов утверждает, что предоставляет случайные числа, сгенерированные из действительно случайного источника, при этом многие из них предоставляют дополнительные услуги рандомизации:

Хорошо известные API ГПСЧ

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

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

  1. ^ Фон Нейман, Джон (1951). «Различные методы, используемые в связи со случайными цифрами» (PDF). Национальное бюро стандартов серии по прикладной математике. 12: 36–38.
  2. ^ Некоторые статьи фон Неймана 1949 года были напечатаны только в 1951 году. Джон фон Нейман, «Различные методы, используемые в связи со случайными числами», в A.S. Хаусхолдер, Г. Форсайт и Х.Х. Жермонд, ред., Метод Монте-Карло, серия Национального бюро стандартов по прикладной математике, т. 12 (Вашингтон, округ Колумбия: типография правительства США, 1951 г.): стр. 36–38.
  3. ^ Лемер, Деррик Х. (1951). «Математические методы в крупномасштабных вычислительных устройствах». Труды 2-го симпозиума по крупномасштабной цифровой вычислительной технике: 141–146.
  4. ^ Томсон, У. Э. (1958). «Модифицированный метод сравнения для генерации псевдослучайных чисел». Компьютерный журнал. 1 (2): 83. Дои:10.1093 / comjnl / 1.2.83.
  5. ^ Ротенберг, А. (1960). «Новый генератор псевдослучайных чисел». Журнал ACM. 7 (1): 75–77. Дои:10.1145/321008.321019.
  6. ^ Д. Э. Кнут, Искусство программирования, Vol. 2 получисленных алгоритма, 3-е изд., Аддисон Уэсли Лонгман (1998); См. Стр. 27.
  7. ^ Tausworthe, R. C. (1965). «Случайные числа, порожденные линейным повторением по модулю два» (PDF). Математика вычислений. 19 (90): 201–209. Дои:10.1090 / S0025-5718-1965-0184406-1.
  8. ^ Wichmann, Brian A .; Хилл, Дэвид I. (1982). «Алгоритм AS 183: эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 31 (2): 188–190. Дои:10.2307/2347988. JSTOR  2347988.
  9. ^ «Поддержка Microsoft - Описание функции СЛЧИС в Excel». 17 апреля 2018.
  10. ^ «Документация» Стандартная библиотека Python »9. Числовые и математические модули» 9.6. Random - Генерация псевдослучайных чисел ».
  11. ^ Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Ред. Мод. Phys. 55 (3): 601–644. Bibcode:1983РвМП ... 55..601Вт. Дои:10.1103 / RevModPhys.55.601.
  12. ^ Эйхенауэр, Юрген; Лен, Юрген (1986). «Нелинейный генератор конгруэнтных псевдослучайных чисел». Statistische Hefte. 27: 315–326. Дои:10.1007 / BF02932576.
  13. ^ Парк, Стивен К .; Миллер, Кейт В. (1988). «Генераторы случайных чисел: трудно найти хороших» (PDF). Коммуникации ACM. 31 (10): 1192–1201. Дои:10.1145/63039.63042.
  14. ^ Викрамаратна, Р. С. (1989). «ЖЕЛУДОЙ - новый метод генерации последовательностей равномерно распределенных псевдослучайных чисел». Журнал вычислительной физики. 83 (1): 16–31. Bibcode:1989JCoPh..83 ... 16 Вт. Дои:10.1016/0021-9991(89)90221-0.
  15. ^ Викрамаратна, Р. Теоретические и эмпирические результаты сходимости для генераторов аддитивных конгруэнтных случайных чисел, Журнал вычислительной и прикладной математики (2009), DOI: 10.1016 / j.cam.2009.10.015
  16. ^ Саввиди, Г.К .; Тер-Арутюнян-Саввиди, Н.Г. (1991). «О моделировании физических систем Монте-Карло». Журнал вычислительной физики. 97 (2): 566. Bibcode:1991JCoPh..97..566S. Дои:10.1016 / 0021-9991 (91) 90015-Д.
  17. ^ а б Джордж, Марсалья; Заман, Ариф (1991). «Новый класс генераторов случайных чисел». Анналы прикладной вероятности. 1 (3): 462–480. Дои:10.1214 / aoap / 1177005878.
  18. ^ Мартин, Люшер (1994). «Портативный высококачественный генератор случайных чисел для моделирования теории поля на решетке». Компьютерная физика Коммуникации. 79 (1): 100–110. arXiv:геп-лат / 9309020. Bibcode:1994CoPhC..79..100L. Дои:10.1016/0010-4655(94)90232-1.
  19. ^ Мэтьюз, Роберт А. Дж. (1992). «Максимально периодические обратные». Бык. Inst. Математика. Приложение. 28: 147–148.
  20. ^ Марсалья, Джордж; Заман, Ариф (1993). «Генератор KISS». Технический отчет, Департамент статистики, Государственный университет Флориды, Таллахасси, Флорида, США.
  21. ^ Сообщение Джорджа Марсальи в группе новостей sci.stat.math от 1 августа 2018 г. с заголовком 'Еще один ГСЧ '.
  22. ^ Коч, Джемаль (1995). «Повторяющиеся с переносом последовательности». Журнал прикладной теории вероятностей. 32 (4): 966–971. Дои:10.2307/3215210. JSTOR  3215210.
  23. ^ От кутюр, Раймонд; L'Ecuyer, Пьер (1997). "Распределительные свойства генераторов случайных чисел умножения с переносом" (PDF). Математика вычислений. 66 Число. 218 (218): 591–607. Bibcode:1997MaCom..66..591C. Дои:10.1090 / S0025-5718-97-00827-2.
  24. ^ Matsumoto, M .; Нисимура, Т. (1998). "MersenneTwister: Генератор однородных псевдослучайных чисел с равномерным распределением A623". Транзакции ACM по моделированию и компьютерному моделированию. 8 (1): 3–30. CiteSeerX  10.1.1.215.1141. Дои:10.1145/272991.272995.
  25. ^ Марсалья, Джордж (Июль 2003 г.). "Xorshift RNGs". Журнал статистического программного обеспечения. 8 (14). Дои:10.18637 / jss.v008.i14.
  26. ^ Panneton, François O .; l'Ecuyer, Пьер; Мацумото, Пьер (март 2006 г.). «Улучшенные долгопериодические генераторы на основе линейных повторений по модулю 2» (PDF). Транзакции ACM на математическом ПО. 32 (1): 1–16. CiteSeerX  10.1.1.73.5499. Дои:10.1145/1132973.1132974.CS1 maint: ref = harv (связь)
  27. ^ Дженкинс, Боб (2009). «Небольшой некриптографический ГПСЧ».
  28. ^ а б c Лосось, Джон; Мораес, Марк; Дрор, Рон; Шоу, Дэвид (2011). «Параллельные случайные числа: так же просто, как 1, 2, 3». Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению данных и анализу 2011 г., статья № 16. Дои:10.1145/2063384.2063405.
  29. ^ Стил, Гай Л. мл .; Ли, Дуг; Флуд, Кристин Х. (2014). «Быстро разделяемые генераторы псевдослучайных чисел» (PDF). OOPSLA '14 Труды Международной конференции ACM 2014 по языкам и приложениям систем объектно-ориентированного программирования.
  30. ^ О'Нил, Мелисса Э. (2014). «PCG: семейство простых быстрых эффективных с точки зрения пространства статистически хороших алгоритмов для генерации случайных чисел» (PDF). Технический отчет.
  31. ^ Кукман, Ричард (2016). "генератор битов случайного цикла (rcb_generator)". Технический отчет.
  32. ^ Видинский, Бернард (2017). "Последовательность Вейля в среднем квадрате ГСЧ". arXiv:1704.00358v5 [cs.CR ].
  33. ^ Блэкман, Дэвид; Винья, Себастьяно (2018). "Скремблированные линейные генераторы псевдослучайных сигналов". arXiv:1805.01407 [cs.DS ].
  34. ^ Harase, S .; Кимото, Т. (2018). "Реализация 64-битного максимально равнораспределенного F2-Линейные генераторы с периодом простоты Мерсенна ". Транзакции ACM на математическом ПО. 44 (3): 30:1–30:11. arXiv:1505.06582. Дои:10.1145/3159444.
  35. ^ Видинский, Бернард (2020). «Квадраты: быстрый ГСЧ на основе счетчиков». arXiv:2004.06278v2 [cs.DS ].
  36. ^ Генератор истинных случайных чисел с использованием коронного разряда: Патентное ведомство Индии, номер заявки на патент: 201821026766
  37. ^ Томас Сымул; Сайед М. Асад; Пинг Кой Лам (2011-06-07), «Демонстрация в реальном времени генерации квантовых случайных чисел с высокой скоростью передачи данных с помощью когерентного лазерного света», Письма по прикладной физике, 98 (23): 231103, arXiv:1107.4438, Bibcode:2011ApPhL..98w1103S, Дои:10.1063/1.3597793

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