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

Question

Каков наилучший способ создать лучший генератор псевдослучайных чисел? (любой язык работает)

Answer 1

Лучший способ создать один - не делать этого.

Генераторы псевдослучайных чисел являются очень сложным предметом, поэтому лучше использовать реализации, созданные людьми, которые хорошо понимают предмет.

Answer 2

Все зависит от приложения. Например, генератор, который создает «наиболее случайные» числа, может быть не самым быстрым или наиболее экономичным по памяти.

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

Обновление : с момента написания этого ответа было опубликовано семейство алгоритмов PCG , которое, по-видимому, превосходит существующие некриптографические алгоритмы на большинстве фронтов (скорость, память, случайность и период ), что делает его отличным универсальным выбором для всего, что угодно , но для криптографии .

Если вы делаете криптографию, мой ответ остается: не сверните свой собственный.

Answer 3

Немецкий журнал C't протестировал ряд программных и аппаратных генераторов в выпуске 2/2009 и проверил результаты с помощью различных статистических тестов.

Я отсканировал результаты здесь .

Я бы не стал писать свои собственные. В статье упоминается, что даже Дональд Кнут потерпел неудачу со своим «Генератором супер-случайных чисел», который в конце концов не был настолько случайным. Получить тот, который прошел все тесты (имел результат> 0 во всех столбцах). Они также протестировали установку с VIA EPIA M10000 mobo, который имеет аппаратный RNG. Мне нравится эта опция для коммерческой или полукоммерческой установки, которая требует надежного сервера случайных чисел с высокой пропускной способностью.

Если, конечно, вы просто играете, в этом случае этого может быть достаточно.

Answer 4

Алгоритмы PRNG сложны, так как приобретают правильные источники энтропии, чтобы заставить их работать хорошо. Это не то, что вы хотите сделать сами. Каждый современный язык имеет библиотеку PRNG, которая почти наверняка подойдет для вашего использования.

Answer 5

Yikes, это может усложнить VEEEEEERY! Кажется, есть ряд метрик для того, чтобы измерить «случайность» генератора случайных чисел, поэтому трудно определить, какие из них «лучшие». Я бы начал с Числовые рецепты в C (или любой другой язык, на котором вы можете найти один) для нескольких примеров. Я написал свой первый простой пример из приведенных там примеров.

РЕДАКТИРОВАТЬ: Важно также начать с определения того, насколько сложным должен быть ваш генератор случайных чисел. Я помню грубое пробуждение, которое я испытал в C несколько лет назад, когда обнаружил, что генератор случайных чисел по умолчанию имеет период где-то около 32 767, что означает, что он имел тенденцию повторяться периодически после генерации такого количества чисел! Если вам нужно несколько бросков кубиков, это нормально. Но не тогда, когда вам нужно генерировать миллионы «случайных» значений для симуляции.

Answer 6

См. Эту ссылку для набора тестов TestU01, который включает в себя несколько батарей тестов.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

В статье автор демонстрирует результаты теста на различных существующих RNG, но не на .NET System.Random (насколько я могу судить). Хотя он тестирует генератор VB6.

Очень немногие проходят все испытания ...

Answer 7

См. Подводные камни при генерации случайных чисел

Answer 8

Если вы собираетесь работать в C ++, Boost имеет коллекцию PRNG, которым я бы доверял гораздо больше, чем что бы то ни было в стандартных библиотеках. Документация может быть полезна при ее выборе. Как всегда, насколько хорош PRNG, зависит от того, для чего вы его используете.

Answer 9

Воровать из кнута полугруппы. Это высокое качество и простота реализации. Он использует пару массивов, сложение и пару ifs. Дешевый, эффективный и хороший длительный период 2 ^ 55, если я правильно помню.

Answer 10

Мои любимые Аппаратные генераторы случайных чисел