Войти
Генераторы случайных чисел важны во многих видах технических приложений, включая физика, инженерия или математика компьютерные исследования (например, моделирование Монте-Карло ), криптография и азартные игры (на игровых серверах ).
В этот список входит множество распространенных типов, независимо от качества.
При использовании генератора псевдослучайных чисел имейте в виду John von Изречение Неймана : «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха».
Следующие ниже алгоритмы являются генераторами псевдослучайных чисел.
| Генератор | Дата | Первые сторонники | Ссылки | Примечания |
|---|---|---|---|---|
| Метод среднего квадрата | 1946 | Дж. фон Нейман | В своем первоначальном виде он низкого качества и представляет только исторический интерес. | |
| Генератор Лемера | 1951 | D. Х. Лемер | Один из самых ранних и влиятельных дизайнов. | |
| Линейный конгруэнтный генератор (LCG) | 1958 | W. Э. Томсон; А. Ротенберг | Обобщение генератора Лемера и исторически наиболее влиятельный и изученный генератор. | |
| Генератор Фибоначчи с запаздыванием (LFG) | 1958 | G. Дж. Митчелл и Д. П. Мур | ||
| Регистр сдвига с линейной обратной связью (LFSR) | 1965 | R. К. Таусворте | Очень влиятельный дизайн. Также называется генераторами Tausworthe. | |
| Генератор Вичмана – Хилла | 1982 | Б. A. Wichmann и D. I. Hill | Комбинация трех небольших LCG, подходящая для 16-битных ЦП. Широко используется во многих программах, например он используется в Excel 2003 и более поздних версиях для функции RAND и был генератором по умолчанию на языке Python до версии 2.2. | |
| Правило 30 | 1983 | S. Вольфрам | На основе клеточных автоматов. | |
| Инверсивный конгруэнтный генератор (ICG) | 1986 | J. Эйхенауэр и Дж. Лен | ||
| Генератор Парка-Миллера | 1988 | С. К. Парк и К. В. Миллер | Конкретная реализация генератора Лемера, широко используемого, поскольку встроена в языки C и C ++ как функция `minstd '. | |
| Генератор желудя | (обнаружен в 1984 г.) 1989 | R. С. Викрамаратна | Генератор чисел A dditive Co ngruential R andom N . Просто реализовать, быстро, но малоизвестно. При соответствующей инициализации проходит все текущие эмпирические наборы тестов и формально доказывает сходимость. Легко продлить на произвольную длину периода и улучшить статистические характеристики для более высоких измерений и с более высокой точностью. | |
| Генератор MIXMAX | 1991 | G. К. Саввиди и Н. Г. Тер-Арутюнян-Саввиди | Он принадлежит к классу матричных линейных конгруэнтных генераторов, обобщению LCG. Обоснование семейства генераторов MIXMAX опирается на результаты эргодической теории и классической механики. | |
| Добавление с переносом (AWC) | 1991 | G. Марсалья и А. Заман | Модификация генераторов Фибоначчи с запаздыванием. | |
| Вычесть с займом (SWB) | 1991 | G. Марсалья и А. Заман | Модификация генераторов Фибоначчи с запаздыванием. Генератор SWB является основой для генератора RANLUX, широко используемого, например, для моделирования физики элементарных частиц. | |
| Максимально периодические обратные величины | 1992 | R. А. Дж. Мэтьюз | Метод, уходящий корнями в теорию чисел, но никогда не использовавшийся на практике. | |
| КИСС | 1993 | Г. Marsaglia | Прототип генератора комбинаций. | |
| Умножение с переносом (MWC) | 1994 | G. Марсалья; К. Коч | ||
| Дополнительное умножение с переносом (CMWC) | 1997 | R. Couture и П. Л'Экуайе | ||
| Мерсенн Твистер (MT) | 1998 | М. Мацумото и Т. Нисимура | Тесно связаны с LFSR. В его реализации MT19937, вероятно, наиболее часто используется современный ГПСЧ. Генератор по умолчанию в R и языке Python, начиная с версии 2.3. | |
| Xorshift | 2003 | G. Marsaglia | Это очень быстрый подтип генераторов LFSR. Марсалья также предложил в качестве усовершенствования генератор xorwow, в котором выходной сигнал генератора xorshift добавлен с помощью последовательности Вейля. Генератор xorwow является генератором по умолчанию в библиотеке CURAND интерфейса прикладного программирования nVidia CUDA для графических процессоров. | |
| Равнораспределенный длиннопериодный линейный (WELL) | 2006 | F. Паннетон, П. Л'Экуайер и М. Мацумото | LFSR, тесно связанный с Mersenne Twister, направленный на исправление некоторых из его недостатков. | |
| Небольшой некриптографический PRNG (JSF) | 2007 | Боб Дженкинс | ||
| Расширенная система рандомизации (ARS) | 2011 | J. Салмон, М. Мораес, Р. Дрор и Д. Шоу | Упрощенная версия блочного шифра AES, обеспечивающая очень высокую производительность в системе, поддерживающей AES-NI. | |
| Threefry | 2011 | Дж. Салмон, М. Мораес, Р. Дрор и Д. Шоу | Упрощенная версия блочного шифра Threefish, подходящая для реализации на GPU. | |
| Филокс | 2011 | Дж. Салмон, М. Мораес, Р. Дрор и Д. Шоу | Упрощение и модификация блочного шифра Threefish с добавлением S-блока. | |
| SplitMix | 2014 | Г. Л. Стил, Д. Ли и К. Х. Флуд | На основе функции окончательного микширования MurmurHash3. Входит в Java Development Kit 8 и выше. | |
| Генератор конгруэнтной перестановки (PCG) | 2014 | M. Э. О'Нил | Модификация LCG. | |
| Генератор битов случайного цикла (RCB) | 2016 | R. Кукман | RCB описывается как генератор битовых последовательностей, созданный для преодоления некоторых недостатков Mersenne Twister и ограничения коротких периодов / битовой длины генераторов сдвига / модуля. | |
| Последовательность Вейля в среднем квадрате ГПСЧ | 2017 | B. Видински | Вариант исходного метода среднего квадрата Джона фон Неймана, этот генератор может быть самым быстрым ГПСЧ, который проходит все статистические тесты. | |
| Ксороширо128 + | 2018 | Д. Блэкман, С. Винья | Модификация генераторов Marsaglia Xorshift, одного из самых быстрых генераторов на современных 64-битных процессорах. Связанные генераторы включают xoroshiro128 **, xoshiro256 + и xoshiro256 **. | |
| 64-битный MELG | 2018 | S. Харасе, Т. Кимото | Реализация 64-битных максимально равнораспределенных F 2 -линейных генераторов с простым периодом Мерсенна. | |
| Квадраты ГСЧ | 2020 | B. Видински | A основанная на счетчике версия Последовательности Вейля в среднем квадрате ГПСЧ. По словам автора, это один из самых быстрых генераторов на основе счетчиков. |
Алгоритмы шифрования и криптографические хэши могут использоваться в качестве генераторов псевдослучайных чисел очень высокого качества. Однако обычно они значительно медленнее (обычно в 2–10 раз), чем быстрые некриптографические генераторы случайных чисел.
К ним относятся:
Некоторые криптографически безопасные генераторы псевдослучайных чисел не полагаются на алгоритмы шифрования, а пытаются математически связать сложность отличия их вывода от "истинного" случайного потока с вычислительно сложной задачей. Эти подходы теоретически важны, но слишком медленны, чтобы их можно было использовать в большинстве приложений. К ним относятся:
Эти подходы комбинируют генератор псевдослучайных чисел (часто в форме блочного или потокового шифра) с внешним источником случайности (например, движения мыши, задержка между нажатиями на клавиатуру и т. д.).
/ dev / random - Unix-подобные системыСледующий (неполный) список веб-сайтов утверждает, что предоставляет случайные числа, сгенерированные из действительно случайного источника, при этом многие из них предоставляют дополнительные услуги рандомизации:
/ dev / randomв Unix-подобных системах