✖


Jump to content

Список генераторов случайных чисел

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

ГСЧ — игровой термин, обозначающий генерацию случайных чисел . геймерам, которые хотят добиться неожиданных результатов в своих играх Технология RNG идеально подходит . На основании числа, сгенерированного с помощью алгоритма ГСЧ , ваш оппонент будет атакован соответствующим образом.

Этот список включает в себя множество распространенных типов, независимо от качества или применимости к конкретному варианту использования.

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

[ редактировать ]

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

Генератор Дата Первые сторонники Ссылки Примечания
Метод среднего квадрата 1946 Дж. фон Нейман [1] В своем первоначальном виде он низкого качества и представляет лишь исторический интерес.
Генератор глины 1951 Д. Х. Лемер [2] Один из самых ранних и влиятельных проектов.
Линейный конгруэнтный генератор (ЛКГ) 1958 МЫ Томсон; А. Ротенберг [3] [4] Обобщение генератора Лемера и исторически наиболее влиятельный и изученный генератор.
Генератор Фибоначчи с запаздыванием (LFG) 1958 Дж. Дж. Митчелл и Д. П. Мур [5]
Регистр сдвига с линейной обратной связью (LFSR) 1965 ЖК Таусворт [6] Очень влиятельный дизайн. Также называются генераторами Таусворта.
Генератор Вихмана – Хилла 1982 Б. А. Вихманн и Д. И. Хилл [7] Комбинация трех небольших LCG, подходящая для 16-битных процессоров . Широко используется во многих программах, например, в Excel 2003 и более поздних версиях для функции Excel СЛЧИС. [8] и это был генератор по умолчанию в языке Python до версии 2.2. [9]
Правило 30 1983 С. Вольфрам [10] На основе клеточных автоматов.
Инверсивный конгруэнтный генератор (ИКГ) 1986 Й. Эйхенауэр и Й. Лен [11]
Блюм Блюм Шуб 1986 М. Блюм, Л. Блюм и М. Шуб [12] Блюм-Блюм-Шуб — это алгоритм PRNG, который считается криптографически безопасным. Его база основана на простых числах.
Генератор Парка-Миллера 1988 СК Парк и К.В. Миллер [13] Конкретная реализация генератора Лемера, широко используемая, поскольку она включена в C++ как функция minstd_rand0 начиная с C++11 . [14]
Генератор ЖЕЛУДЯ 1989 г. (обнаружен в 1984 г.) Больница Викрамаратна [15] [16] Аддитивный ​ ​ конгруэнтный ​ случайных чисел генератор .

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

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

См. также

[ редактировать ]

Ссылки

[ редактировать ]
  1. ^ Некоторые из статей фон Неймана 1949 года были напечатаны только в 1951 году. Джон фон Нейман, «Различные методы, используемые в связи со случайными цифрами», в книге AS Householder, GE Forsythe и HH Germond, ред., Метод Монте-Карло, Национальное бюро стандартов. Серия «Прикладная математика» , вып. 12 (Вашингтон, округ Колумбия: Типография правительства США, 1951): стр. 36–38.
  2. ^ Лемер, Деррик Х. (1951). «Математические методы в больших вычислительных устройствах». Материалы 2-го симпозиума по крупномасштабной цифровой вычислительной технике : 141–146.
  3. ^ Томсон, МЫ (1958). «Модифицированный метод сравнения для генерации псевдослучайных чисел» . Компьютерный журнал . 1 (2): 83. дои : 10.1093/comjnl/1.2.83 .
  4. ^ Ротенберг, А. (1960). «Новый генератор псевдослучайных чисел» . Журнал АКМ . 7 (1): 75–77. дои : 10.1145/321008.321019 . S2CID   16770825 .
  5. ^ DE Кнут, Искусство компьютерного программирования, Vol. 2 получисловых алгоритма, 3-е изд., Аддисон Уэсли Лонгман (1998); См. стр. 27.
  6. ^ Таусворт, RC (1965). «Случайные числа, генерируемые линейной рекуррентностью по модулю два» (PDF) . Математика вычислений . 19 (90): 201–209. дои : 10.1090/S0025-5718-1965-0184406-1 .
  7. ^ Вичманн, Брайан А.; Хилл, Дэвид И. (1982). «Алгоритм AS 183: эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика) . 31 (2): 188–190. дои : 10.2307/2347988 . JSTOR   2347988 .
  8. ^ «Поддержка Microsoft — Описание функции СЛЧИС в Excel» . 17 апреля 2018 г.
  9. ^ «Документация » Стандартная библиотека Python » 9. Числовые и математические модули » 9.6. random — Генерация псевдослучайных чисел» .
  10. ^ Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Преподобный Мод. Физ . 55 (3): 601–644. Бибкод : 1983РвМП...55..601Вт . дои : 10.1103/RevModPhys.55.601 .
  11. ^ Эйхенауэр, Юрген; Лен, Юрген (1986). «Нелинейный конгруэнтный генератор псевдослучайных чисел». Статистические буклеты . 27 :315-326. дои : 10.1007/BF02932576 . S2CID   122052399 .
  12. ^ Блюм, Л.; Блюм, М.; Шуб, М. (1 мая 1986 г.). «Простой непредсказуемый генератор псевдослучайных чисел» . SIAM Journal по вычислительной технике . 15 (2): 364–383. дои : 10.1137/0215025 . ISSN   0097-5397 .
  13. ^ Парк, Стивен К.; Миллер, Кейт В. (1988). «Генератор случайных чисел: хорошие найти сложно» (PDF) . Коммуникации АКМ . 31 (10): 1192–1201. дои : 10.1145/63039.63042 . S2CID   207575300 .
  14. ^ «Генерация псевдослучайных чисел» . cppreference.com . Проверено 14 ноября 2021 г.
  15. ^ Викрамаратна, Р.С. (1989). «ЖЕЛУДЬ — новый метод генерации последовательностей равномерно распределенных псевдослучайных чисел». Журнал вычислительной физики . 83 (1): 16–31. Бибкод : 1989JCoPh..83...16W . дои : 10.1016/0021-9991(89)90221-0 .
  16. ^ Викрамаратна, Р.С. Теоретические и эмпирические результаты сходимости аддитивных конгруэнтных генераторов случайных чисел, Журнал вычислительной и прикладной математики (2009), дои : 10.1016/j.cam.2009.10.015
  17. ^ Саввидий, ГК; Тер-Арутюнян-Саввидий, Н.Г. (1991). «О моделировании физических систем Монте-Карло». Журнал вычислительной физики . 97 (2): 566. Бибкод : 1991JCoPh..97..566S . дои : 10.1016/0021-9991(91)90015-D .
  18. ↑ Перейти обратно: Перейти обратно: а б Джордж, Марсалья; Заман, Ариф (1991). «Новый класс генераторов случайных чисел» . Анналы прикладной теории вероятности . 1 (3): 462–480. дои : 10.1214/aoap/1177005878 .
  19. ^ Мартин, Люшер (1994). «Портативный высококачественный генератор случайных чисел для моделирования теории поля на решетке». Компьютерная физика. Коммуникации . 79 (1): 100–110. arXiv : hep-lat/9309020 . Бибкод : 1994CoPhC..79..100L . дои : 10.1016/0010-4655(94)90232-1 . S2CID   17608961 .
  20. ^ Мэтьюз, Роберт Эй Джей (1992). «Максимально периодические обратные величины» . Бык. Инст. Математика. Приложение . 28 : 147–148.
  21. ^ Марсалья, Джордж; Заман, Ариф (1993). «Генератор ПОЦЕЛУЯ». Технический отчет, Департамент статистики, Университет штата Флорида, Таллахасси, Флорида, США .
  22. ↑ Сообщение Джорджа Марсальи в группе новостей sci.stat.math от 1 августа 2018 г. под заголовком « Еще один ГСЧ ».
  23. ^ Коч, Джемаль (1995). «Повторяющиеся последовательности с переносом». Журнал прикладной вероятности . 32 (4): 966–971. дои : 10.2307/3215210 . JSTOR   3215210 . S2CID   123798320 .
  24. ^ Кутюр, Раймонд; Л'Экуйер, Пьер (1997). «Свойства распределения генераторов случайных чисел умножения с переносом» (PDF) . Математика вычислений . 66 номер. 218 (218): 591–607. Бибкод : 1997MaCom..66..591C . дои : 10.1090/S0025-5718-97-00827-2 .
  25. ^ Мацумото, М.; Нисимура, Т. (1998). «MersenneTwister: равнораспределенный равнораспределенный равномерный генератор псевдослучайных чисел A623». ACM-транзакции по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX   10.1.1.215.1141 . дои : 10.1145/272991.272995 . S2CID   3332028 .
  26. ^ Марсалья, Джордж (июль 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14). дои : 10.18637/jss.v008.i14 .
  27. ^ Паннетон, Франсуа О.; л'Экуйер, Пьер; Мацумото, Пьер (март 2006 г.). «Улучшенные долгопериодические генераторы на основе линейных рекуррент по модулю 2» (PDF) . Транзакции ACM в математическом программном обеспечении . 32 (1): 1–16. CiteSeerX   10.1.1.73.5499 . дои : 10.1145/1132973.1132974 . S2CID   7368302 .
  28. ^ Дженкинс, Боб (2009). «Небольшой некриптографический ГПСЧ» .
  29. ↑ Перейти обратно: Перейти обратно: а б с Лосось, Джон; Мораес, Марк; Дрор, Рон; Шоу, Дэвид (2011). «Параллельные случайные числа: просто, как 1, 2, 3». Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу 2011 г., статья № 16 . дои : 10.1145/2063384.2063405 .
  30. ^ Балкова, Любомира; Буччи, Микеланджело; Де Лука, Алессандро; Хладкий, Иржи; Пузынина, Светлана (сентябрь 2016 г.). «Апериодические генераторы псевдослучайных чисел на основе бесконечных слов». Теоретическая информатика . 647 : 85–100. arXiv : 1311.6002 . дои : 10.1016/j.tcs.2016.07.042 . S2CID   2175443 .
  31. ^ Стил, Гай Л. младший; Леа, Дуг; Флад, Кристин Х. (2014). «Генератор псевдослучайных чисел с быстрым расщеплением» (PDF) . OOPSLA '14 Материалы Международной конференции ACM 2014 г. по языкам и приложениям систем объектно-ориентированного программирования .
  32. ^ О'Нил, Мелисса Э. (2014). «PCG: семейство простых быстрых, экономичных и статистически хороших алгоритмов для генерации случайных чисел» (PDF) . Технический отчет .
  33. ^ Кукман, Ричард (2016). «генератор битов случайного цикла (rcb_generator)» . Технический отчет .
  34. ^ Видынски, Бернар (2017). «ГСЧ последовательности Вейля среднего квадрата». arXiv : 1704.00358 [ cs.CR ].
  35. ^ Кнейзель, Рон (2018). Случайные числа и компьютеры (1-е изд.). Спрингер. стр. 13–14. ISBN  9783319776972 .
  36. ^ Блэкман, Дэвид; Винья, Себастьяно (2018). «Скремблированные линейные генераторы псевдослучайных чисел». arXiv : 1805.01407 [ cs.DS ].
  37. ^ Харасе, С.; Кимото, Т. (2018). «Реализация 64-битных максимально равнораспределенных F 2 -линейных генераторов с простым периодом Мерсенна» . Транзакции ACM в математическом программном обеспечении . 44 (3): 30:1–30:11. arXiv : 1505.06582 . дои : 10.1145/3159444 . S2CID   14923086 .
  38. ^ Видынски, Бернар (2020). «Квадраты: быстрый встречный ГСЧ». arXiv : 2004.06278 [ cs.DS ].
  39. ^ Генератор истинных случайных чисел с использованием коронного разряда: Патентное ведомство Индии.Номер заявки на патент: 201821026766.
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=List_of_random_number_generators&oldid=1236376523#Pseudorandom_number_generators_(PRNGs)"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 86a93b7e28119b880bce6638cf680085__1721817480
URL1:https://arc.ask3.ru/arc/aa/86/85/86a93b7e28119b880bce6638cf680085.html
Заголовок, (Title) документа по адресу, URL1:
List of random number generators - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)