Ответ 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 ²¹⁶⁰⁹¹ -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, такой как

• Bernstein ChaCha20, RFC 7539. Альтернативы будут
• У HC-256,
• Дженкинс ISAAC64.

Примечание. В предыдущей версии я заявлял, что алгоритмы Random123 криптографически безопасны, но это не так.

PRNG Тестирование

Точно так же, для статистических испытаний PRNG, в настоящее время уровень техники, вероятно,

• L' Ecuyer TestU01 (с SmallCrush, Crush, BigCrush),
• Doty-Humphrey Pracrand со своим набором PractRand,

в то время как они исторически важны, но устарели:

• 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, он медленный для семян, но достаточно быстрый после посева.

2. ведет себя хорошо даже при очень больших размерах

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

3. имеет чрезвычайно большой период

Определить очень большой?

Пример 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 ¹⁹⁹³⁷ -1 итераций ( > 43 × 10 ⁶⁰⁰⁰), как показано, равнораспределяется в (до) 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 любое другое целочисленное значение в первом массиве, чтобы получить его Базовое обратное и добавить к сумме вместо самого числа все массивы, кроме основного, получают скремблированные (случайные перетасовки) в случайные моменты времени, выбранные из сам случайный пул

Это гарантирует, что в долгосрочном будущем никакие повторяющиеся шаблоны не могут возникнуть или, по крайней мере, намного позже, чем в противном случае, результат будет очень хорошим пулом случайных целых чисел, который имеет ЧРЕЗВЫЧАЙНЫЙ длинный период...