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

Если вы ищете алгоритм, который проходит все статистические тесты, но все еще быстр, вы можете попробовать Xorshift-Algorithm . По сравнению со случайной библиотекой в ​​Java она примерно на 30% быстрее и обеспечивает лучшие результаты. Его Период не такой длинный, как у Мерсенна Твистер, но все же приличный.

Реализация может быть найдена здесь:

http://demesos.blogspot.com/2011/09/replacing-java-random-generator.html

Редактировать

Похоже, что новые варианты XORShift теперь даже превосходят MerseneTwister и WELL по качеству (но не по периодам). Они проходят более эмпирические тесты качества, как это видно в PRNG Shootout .

Они также впечатляют по производительности. Я провел тестирование различных реализаций в Java, источник и результаты здесь: https://github.com/tobijdc/PRNG-Performance

1. проходит все статистические тесты

Каждый 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-битным целочисленным типом ... I думаете, это верно везде, для которого определен тип?)

Это достаточно для любого обычного использования, а также достаточно быстро. Если вам нужно что-то лучше, переключитесь на 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, но в тексте ^ используется для обозначения показателя степени)