Генератор псевдослучайных чисел
Каков наилучший способ создать лучший генератор псевдослучайных чисел? (любой язык работает)
12 ответов
Лучший способ создать это - не делать этого.
Генераторы псевдослучайных чисел являются очень сложным предметом, поэтому лучше использовать реализации, созданные людьми, которые хорошо понимают предмет.
Все зависит от приложения. Например, генератор, который создает "наиболее случайные" числа, может быть не самым быстрым или наиболее экономичным по памяти.
Алгоритм Мерсенна Твистера является популярным, довольно быстрым генератором псевдослучайных чисел, который дает довольно хорошие результаты. У него очень большой период, но также относительно большое состояние (2,5 кБ). Однако это не считается достаточно хорошим для криптографических приложений.
Обновление: поскольку этот ответ был написан, было опубликовано семейство алгоритмов PCG, которое, по-видимому, превосходит существующие не криптографические алгоритмы по большинству направлений (скорость, память, случайность и период), что делает его отличным универсальным выбором для всего, кроме криптографии.
Если вы делаете крипто, хотя, мой ответ остается: не катите свой собственный.
Немецкий журнал C't протестировал ряд программных и аппаратных генераторов в выпуске 2/2009 и проверил результаты с помощью различных статистических тестов.
Я отсканировал результаты здесь.
Я бы не стал писать свои собственные. В статье упоминается, что даже Дональд Кнут потерпел неудачу с его "Генератором супер-случайных чисел", который в конце концов не был настолько случайным. Получить тот, который прошел все тесты (имел результат> 0 во всех столбцах). Они также протестировали установку с VIA EPIA M10000 mobo, который имеет аппаратный RNG. Мне нравится этот вариант для коммерческой или полукоммерческой установки, для которой требуется надежный сервер случайных чисел с высокой пропускной способностью.
Если, конечно, вы просто не играете, в этом случае это может быть достаточно хорошо.
Алгоритмы PRNG сложны, так как приобретают правильные источники энтропии, чтобы заставить их работать хорошо. Это не то, что вы хотите сделать сами. Каждый современный язык имеет библиотеку PRNG, которая почти наверняка подойдет для вашего использования.
Yikes, это может усложнить VEEEEEERY! Кажется, есть ряд метрик для того, чтобы измерить "случайность" генератора случайных чисел, поэтому трудно определить, какие из них "лучшие". Я бы начал с Числовых Рецептов в C (или любого языка, на котором вы можете найти один) для нескольких примеров. Я написал свой первый простой пример из приведенных там примеров.
РЕДАКТИРОВАТЬ: Также важно начать с определения того, насколько сложным вам нужен генератор случайных чисел. Я помню грубое пробуждение, которое я испытал в C несколько лет назад, когда обнаружил, что генератор случайных чисел по умолчанию имеет период где-то около 32 767, что означает, что он имел тенденцию повторяться периодически после генерации такого количества чисел! Если вам нужно несколько бросков кубиков, это нормально. Но не тогда, когда вам нужно генерировать миллионы "случайных" значений для симуляции.
Посмотрите эту ссылку для набора тестов TestU01, который включает в себя несколько батарей тестов.
http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
В статье автор демонстрирует результаты теста на различных существующих RNG, но не на.NET System.Random (насколько я могу судить). Хотя он тестирует генератор VB6.
Очень немногие проходят все испытания...
В рабочем коде определенно безопаснее использовать установленную библиотеку, но понимание того, как работают генераторы псевдослучайных чисел, и написание собственного может быть интересным и полезным с образовательной точки зрения.
Существует множество различных методов, но один из них основан на логистической карте. то есть
x = r * x * (1 - x)
С правильным значением для
r, значения
xдемонстрируют хаотичное и непредсказуемое поведение. Есть подводные камни, о которых вы можете прочитать в ссылках ниже.
использованная литература
Укради один из кнута полугрупповой. Это высокое качество и простота реализации. Он использует пару массивов, сложение и пару ifs. Дешевый, эффективный и хороший длительный период 2^55, если я правильно помню.
Если вы собираетесь работать на C++, у Boost есть коллекция PRNG, которым я бы доверял гораздо больше, чем все, что есть в стандартных библиотеках. Документация может быть полезна при выборе. Как всегда, насколько хорош PRNG, зависит от того, для чего вы его используете.
https://github.com/fsssosei/Pure_PRNG Библиотеки Python для алгоритмов PRNG, которые проходят статистические тесты