Лучший генератор псевдослучайных чисел
На сегодняшний день, который является лучшим генератором псевдослучайных чисел? Лучше всего
Я имею в виду тот, который -
- проходит все статистические тесты
- ведет себя хорошо даже при очень больших размерах
- имеет чрезвычайно большой период
Я могу думать о MT. Есть ли PRNG, который лучше MT? Какой вариант MT лучше всего?
Ответы
Ответ 1
Попробуйте преемник MT: SFMT (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html). Акроним означает SIMD-ориентированный Fast Mersenne Twister.
Он использует векторные инструкции,
например SSE или AltiVec, для ускорения генерации случайных чисел.
Кроме того, он отображает большие периоды, чем исходный MT: SFMT может быть настроен на использование периодов до 2 216091 -1.
Наконец, у MT были некоторые проблемы при неудачной инициализации: он имел тенденцию рисовать много 0, что приводило к случайным числам случайного качества. Эта проблема может длиться до 700000 ничьих, прежде чем компенсируется повторением алгоритма. Как следствие, SFMT также был разработан, чтобы оставить это состояние с избыточным избытком намного быстрее, чем его старший.
Проверьте ссылку, которую я дал в начале этого сообщения, чтобы найти исходный код и научные публикации, описывающие этот алгоритм.
Чтобы определенно вас убедить, вы можете увидеть здесь http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html таблицу, сравнивающую скорости генерации как MT, так и SFMT. В любом случае, SFMT быстрее развивает лучшие качества, чем MT.
- редактировать следующие комментарии -
В более общем плане, когда вы выбираете PRNG, вам нужно учитывать приложение, которое вы разрабатываете. Действительно, некоторые PRNG лучше подходят для некоторых ограничений приложений. Генераторы MT и WELL, например, плохо подходят для криптографических приложений, тогда как они являются лучшим выбором при работе с симуляторами Монте-Карло.
В нашем случае WELL может показаться идеальным благодаря его лучшим свойствам равнораспределения, чем SFMT. Тем не менее, WELL также намного медленнее, и он не может отображать периоды размером с SFMT.
Как вывод, PRNG не может быть заявлен как наилучший для всех приложений, но для конкретного домена и, в частности, при условии.
Ответ 2
Просто быстрое обновление, поскольку ответы показывают их возраст: Сегодня Twister Mersenne больше не считается современным (несколько раздутым, предсказуемым, учитывая всего 624 значения, медленное засевание, возможное неправильное засевание,...).
Нормальный PRNG
Для нормальных приложений, где важны хорошие статистические свойства и скорость, рассмотрите
- Семья О'Нила,
- Скажем, семья Винья Ксороширо xoroshiro128+ (не японское название, а "X-or, вращать, сдвигать, вращать"), и
- DE Shaw Random123 Suite (который включает в себя Philox и хорошо названный ARS, упрощение шифрования бесконечной последовательности нулей с помощью AES-CTR), хотя я не уверен, сколько PRNG Random123 было изучено.
Криптографически безопасный PRNG (CSPRNG)
Для криптографических приложений, где важна непредсказуемость, рассмотрим криптографически безопасный PRNG, такой как
Примечание. В предыдущей версии я заявлял, что алгоритмы Random123 криптографически безопасны, но это не так.
PRNG Тестирование
Точно так же, для статистических испытаний PRNG, в настоящее время уровень техники, вероятно,
в то время как они исторически важны, но устарели:
- Marsaglia DieHard, DieHarder,
- NIST 800-22 А.
Ответ 3
Если вы ищете алгоритм, который проходит все статистические тесты, но все же быстро, вы можете попробовать Xorshift-Algorithm. По сравнению со случайной библиотекой в Java она на 30% быстрее и обеспечивает лучшие результаты. Его Период не такой длинный, как Мерсенн Твистер, но его по-прежнему достойный.
Реализация можно найти здесь:
http://demesos.blogspot.com/2011/09/replacing-java-random-generator.html
Edit
Кажется, что новые варианты XORShift теперь даже избили MerseneTwister и WELL по качеству (но не в период). Они проходят более эмпирические тесты качества, которые можно увидеть в PRNG Shootout.
Они впечатляют и в производительности.
Я сделал контрольный пример различных реализаций на Java, источник и результаты здесь:
https://github.com/tobijdc/PRNG-Performance
Ответ 4
Ну, WELL-генератор является обобщением и улучшением MT-19937.
Ответ 5
- проходит все статистические тесты
Каждый PRNG, упомянутый в других ответах, до сих пор широко относится к семейству PRNG GFSR/LFSR. Все они не соответствуют бинарному рангу матрицы и, возможно, линейным испытаниям сложности.
Есть много многих PRNG, которые проходят все статистические тесты общего назначения, но по какой-то причине люди, похоже, считают GFSR более сексуальными.
Вот пример PRNG, который передает все статистические тесты общего назначения, но не криптографически безопасен:
static unsigned long long rng_a, rng_b, rng_c, rng_counter;
unsigned long long rng64() {
unsigned long long tmp = rng_a + rng_b + rng_counter++;
rng_a = rng_b ^ (rng_b >> 12);
rng_b = rng_c + (rng_c << 3);
rng_c = ((rng_c << 25) | (rng_c >> (64-25))) + tmp;
return tmp;
}
void seed(unsigned long long s) {
rng_a = rng_b = rng_c = s; rng_counter = 1;
for (int i = 0; i < 12; i++) rng64();
}
(Это предполагает, что long long является 64-битным целым типом... Я думаю, что true везде, где этот тип определен для?)
Это адекватно для любого нормального использования и довольно быстро. Если вам нужно что-то лучше, переключитесь на CSPRNG - они, как правило, намного лучше, чем любой некритичный PRNG. ChaCha (http://cr.yp.to/chacha.html), например, является сплошной CSPRNG с быстрым посевом, произвольным доступом и регулируемым качеством. HC-256 (http://en.wikipedia.org/wiki/HC-256) - это еще более качественный CSPRNG, он медленный для семян, но достаточно быстрый после посева.
- ведет себя хорошо даже при очень больших размерах
Это в значительной степени эквивалентно точке # 1. Кроме того, пример PRNG, предложенный мной, относится к хаотическому типу - такие PRNG, когда они плохо себя ведут, делают это при небольшом количестве измерений, а не в больших количествах.
- имеет чрезвычайно большой период
Определить очень большой?
Пример PRNG, предложенный выше, имеет доказуемый минимальный период 2 ^ 64 и средний период 2 ^ 255 и пространство состояний 2 ^ 256. Для двух CSPRNG, которые я связывал, ChaCha имеет период 2 ^ 68 и пространство состояний 2 ^ 260, а HC-256 имеет средний период где-то порядка 2 ^ 65000 или около того IIRC и предлагает вероятностное доказательство того, что его кратчайший цикл длиннее 2 ^ 128 с вероятностью больше 1- (2 ^ -128) и имеет пространство состояний около 2 ^ 65000.
На практике период не имеет значения примерно за 2 ^ 60, и даже это маргинально. Обычно причина, по которой люди просят высокий период, состоит в том, что либо они не знают, о чем они говорят, либо потому, что им нужно большое пространство состояний (которое, по крайней мере, равно периоду, но часто больше), что может быть полезно около 2 ^ 250. Но большое пространство состояний не очень помогает, если вы не посеяли нечто большее, чем одно целое, чего большинство людей этого не делает.
(обратите внимание: в коде символ ^ используется для обозначения xor, но в тексте ^ используется показатель степени)
Ответ 6
Похоже, что MT соответствует вашим критериям:
Он имеет колоссальный период 2 19937 -1 итераций ( > 43 × 10 6000), как показано, равнораспределяется в (до) 623 измерениях (для 32-битные значения) и работает быстрее, чем другие статистически разумные генераторы
(Из: Википедия)
The Mersenne Twister является одним из наиболее широко протестированных генераторов случайных чисел. Однако, будучи полностью детерминированным, он не подходит для всех целей и совершенно непригоден для криптографических целей.
(Из: Документы Python)
И wikipedia есть что сказать о криптографически защищенных prng, если это ваш интерес.
Ответ 7
вот еще один генератор случайных чисел, который вы могли бы построить, который прошел бы все тесты генерации случайных чисел, использует массивы Prime number Length для всех простых чисел в определенном диапазоне, это использует несколько массивов, но поскольку многие из них будут небольшими, здесь нет настоящей большой проблемы, поместите значения в каждый из массивов, которые заполняют их всеми случайными данными семян
затем добавьте все значения в каждом из массивов отдельно, используя базовую инверсию M
где M является базой чисел в этом конкретном массиве, КАЖДЫЙ ДРУГОЙ ЧЛЕН ЧЕРЕЗ, возьмите СУММ всех этих
ответы или выходы и MOD его с основной базой, используемой для всех массивов
(также для каждого массива Значения выпадают с левой или нижней стороны по мере создания новых значений, перемещая все значения в сторону нижнего конца массива.
Основной массив был бы самым большим массивом длины первичного номера. Получившийся период был бы
произведение всех длин этих массивов с длинными номерами.
и, скорее всего, числа будут проходить все или большинство тестов случайности и быть довольно случайными.
Ответ 8
rand() является лучшим (используется в моем собственном FlipCoinPRNG)
- Четырехминутный тест = PASSED!
- Тесты Diehard = PASSED!
- NIST SP800-22rev1a (все тесты) = PASSED!
Ответ 9
Я думаю, что моя лучшая или потенциально может быть она использует технологии и математику, которые еще не были разработаны, но только я и я и я
У меня нет имени для него, но он полностью целочисленный, основанный на нем root, и он использует алгоритм и математику, которые я разработал сам. Я полностью ее протестировал на различных тестовых сайтах
в основном у вас есть массив целых чисел в любой заданной базе, вы добавляете числа и модифицируете конечный результат используемой базой.
За мной до сих пор??? то вы используете один или два других массива с некоторыми произвольно случайными числами в них и добавляете их к каждому элементу массива по мере его добавления, кроме того
вы можете BASE INVERT любое другое целочисленное значение в первом массиве, чтобы получить его Базовое обратное и добавить к сумме вместо самого числа все массивы, кроме основного, получают скремблированные (случайные перетасовки) в случайные моменты времени, выбранные из сам случайный пул
Это гарантирует, что в долгосрочном будущем никакие повторяющиеся шаблоны не могут возникнуть или, по крайней мере, намного позже, чем в противном случае, результат будет очень хорошим пулом случайных целых чисел, который имеет ЧРЕЗВЫЧАЙНЫЙ длинный период...