На сегодняшний день, который является лучшим генератором псевдослучайных чисел? Лучше всего Я имею в виду тот, который -
Я могу думать о MT. Есть ли PRNG, который лучше MT? Какой вариант MT лучше всего?
Попробуйте преемник 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 не может быть заявлен как наилучший для всех приложений, но для конкретного домена и, в частности, при условии.
Просто быстрое обновление, поскольку ответы показывают их возраст: Сегодня Twister Mersenne больше не считается современным (несколько раздутым, предсказуемым, учитывая всего 624 значения, медленное засевание, возможное неправильное засевание,...).
Для нормальных приложений, где важны хорошие статистические свойства и скорость, рассмотрите
Для криптографических приложений, где важна непредсказуемость, рассмотрим криптографически безопасный PRNG, такой как
Примечание. В предыдущей версии я заявлял, что алгоритмы Random123 криптографически безопасны, но это не так.
Точно так же, для статистических испытаний PRNG, в настоящее время уровень техники, вероятно,
в то время как они исторически важны, но устарели:
Если вы ищете алгоритм, который проходит все статистические тесты, но все же быстро, вы можете попробовать 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
Ну, WELL-генератор является обобщением и улучшением MT-19937.
- проходит все статистические тесты
Каждый 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, но в тексте ^ используется показатель степени)
Похоже, что MT соответствует вашим критериям:
Он имеет колоссальный период 2 19937 -1 итераций ( > 43 × 10 6000), как показано, равнораспределяется в (до) 623 измерениях (для 32-битные значения) и работает быстрее, чем другие статистически разумные генераторы
The Mersenne Twister является одним из наиболее широко протестированных генераторов случайных чисел. Однако, будучи полностью детерминированным, он не подходит для всех целей и совершенно непригоден для криптографических целей.
И wikipedia есть что сказать о криптографически защищенных prng, если это ваш интерес.
вот еще один генератор случайных чисел, который вы могли бы построить, который прошел бы все тесты генерации случайных чисел, использует массивы Prime number Length для всех простых чисел в определенном диапазоне, это использует несколько массивов, но поскольку многие из них будут небольшими, здесь нет настоящей большой проблемы, поместите значения в каждый из массивов, которые заполняют их всеми случайными данными семян
затем добавьте все значения в каждом из массивов отдельно, используя базовую инверсию M где M является базой чисел в этом конкретном массиве, КАЖДЫЙ ДРУГОЙ ЧЛЕН ЧЕРЕЗ, возьмите СУММ всех этих ответы или выходы и MOD его с основной базой, используемой для всех массивов (также для каждого массива Значения выпадают с левой или нижней стороны по мере создания новых значений, перемещая все значения в сторону нижнего конца массива.
Основной массив был бы самым большим массивом длины первичного номера. Получившийся период был бы произведение всех длин этих массивов с длинными номерами. и, скорее всего, числа будут проходить все или большинство тестов случайности и быть довольно случайными.
rand() является лучшим (используется в моем собственном FlipCoinPRNG)
Я думаю, что моя лучшая или потенциально может быть она использует технологии и математику, которые еще не были разработаны, но только я и я и я У меня нет имени для него, но он полностью целочисленный, основанный на нем root, и он использует алгоритм и математику, которые я разработал сам. Я полностью ее протестировал на различных тестовых сайтах в основном у вас есть массив целых чисел в любой заданной базе, вы добавляете числа и модифицируете конечный результат используемой базой.
За мной до сих пор??? то вы используете один или два других массива с некоторыми произвольно случайными числами в них и добавляете их к каждому элементу массива по мере его добавления, кроме того вы можете BASE INVERT любое другое целочисленное значение в первом массиве, чтобы получить его Базовое обратное и добавить к сумме вместо самого числа все массивы, кроме основного, получают скремблированные (случайные перетасовки) в случайные моменты времени, выбранные из сам случайный пул
Это гарантирует, что в долгосрочном будущем никакие повторяющиеся шаблоны не могут возникнуть или, по крайней мере, намного позже, чем в противном случае, результат будет очень хорошим пулом случайных целых чисел, который имеет ЧРЕЗВЫЧАЙНЫЙ длинный период...