Closed. This question is opinion-based. It is not currently accepting answers.

Want to improve this question? Update the question so it can be answered with facts and citations by editing this post.

开发者_如何学C

Closed 1 year ago.

Improve this question

By best I mean the one that:

passes all statistical tests
behaves well even at very high dimensions
has an extremely large period

I can think of Mersenne Twister, but which variant is the best? Is there any better PRNG?

Just a quick update, as the answers show their age: Today the Mersenne Twister is not really considered state of the art anymore (somewhat bloated, predictable given just 624 values, slow to seed, bad seeding possible, ...).

Normal PRNG

For normal applications, where good statistical properties and speed are important, consider

O'Neill's PCG family,
Vigna's xoroshiro family, say xoroshiro128+ (not a Japanese name btw, but "X-or, rotate, shift, rotate"), and
D. E. Shaw's Random123 suite (which includes Philox and the nicely named ARS, a simplification of encrypting an infinite sequence of zeros with AES-CTR), though I'm not sure how much the Random123 PRNG have been scrutinised.

Cryptographically secure PRNG (CSPRNG)

For cryptographic applications, where non-predictability is important, consider a cryptographically secure PRNG, such as

Bernstein's ChaCha20, RFC 7539. Alternatives would be
Wu's HC-256,
Jenkins's ISAAC64.

Note: In a previous version I stated that the Random123 algorithms are cryptographically secure, but they're not.

PRNG Testing

Similarly, for statistical tests of PRNG, nowadays the state of the art is probably

L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush),
Doty-Humphrey's pracrand with its PractRand suite,

while these are historically important, but outdated:

Marsaglia's DieHard, DieHarder,
NIST 800-22 A.

Try MT's successor: SFMT ( http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html ). The acronym stands for SIMD-oriented Fast Mersenne Twister. It uses vector instructions, like SSE or AltiVec, to quick up random numbers generation.

Moreover it displays larger periods than the original MT: SFMT can be configured to use periods up to 2²¹⁶⁰⁹¹ -1.

Finally, MT had some problems when badly initialized: it tended to draw lots of 0, leading to bad quality random numbers. This problem could last up to 700000 draws before being compensated by the recurrence of the algorithm. As a consequence, SFMT has also been designed to leave this zero-excess state much quicker than its elder.

Check the link I've given at the beginning of this post to find the source code and the scientific publications describing this algorithm.

In order to definitely convince you, you can see here http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html a table comparing generation speeds of both MT and SFMT. In any case, SFMT is quicker while laying out better qualities than MT.

-- edit following commentaries --

More generally, when you're choosing a PRNG, you need to take into account the application you're developing. Indeed, some PRNGs fit better to some applications constraints. MT and WELL generators for instance aren't well suited for cryptographic applications, whereas they are the best choice when dealing with Monte Carlo Simulations.

In our case, WELL may seem ideal thanks to its better equidistribution properties than SFMT. Nonetheless, WELL is also far slower and he's not able to display periods as large as SFMT.

As a conclusion, a PRNG cannot be stated as best for all the applications, but for a particular domain and in particular circumstances withal.

passes all statistical tests

Every PRNG mentioned in other responses so far broadly belongs to the GFSR/LFSR family of PRNGs. All of them fail binary matrix rank and probably linear complexity tests.

There are many many PRNGs that pass all general purpose statistical tests, but for some reason people seem to find GFSRs sexier.

Here is a sample PRNG that passes all general purpose statistical tests, but is not cryptographically secure:

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();
}

(That assumes that long long is a 64 bit integer type... I think that's true everywhere that type is defined for?)

That's adequate for any normal use, and fairly fast as well. If you need something better, switch to a CSPRNG - they tend to be far better than any non-crypto PRNG. ChaCha ( http://cr.yp.to/chacha.html ), for example, is a solid CSPRNG with fast seeding, random access, and adjustable quality. HC-256 ( http://en.wikipedia.org/wiki/HC-256 ) is an even higher quality CSPRNG, it's slow to seed but reasonably fast once seeded.

behaves well even at very high dimensions

That's pretty much equivalent to point #1. Also, the example PRNG I offered is of the chaotic type - such PRNGs, when they misbehave, do so at small numbers of dimensions, not large numbers.

has an extremely large period

Define extremely large?

The example PRNG I offered above has a provable minimum period of 2^64 and an average period of 2^255 and a statespace of 2^256. For the two CSPRNGs I linked, ChaCha has a period of 2^68 and statespace of 2^260, and HC-256 has an average period somewhere on the order of 2^65000 or so IIRC and offers a probabilistic proof that its shortest cycle is longer than 2^128 with likelihood greater than 1-(2^-128) and it has a statespace around 2^65000.

In practice, period doesn't matter beyond about 2^60, and even that is marginal. Usually the reason why people ask for high period is because either they don't know what they're talking about or because they need a large statespace (which is at least equal to the period, but often larger), which can be beneficial up to around 2^250. But a large statespace isn't much help unless you are seeding from something bigger than a single integer, which most people don't.

(note: in the code, ^ is used to mean xor, but in the text ^ is used to mean exponent)

If you look for an algorithm, that passes all statistical tests, but is still fast you could try the Xorshift-Algorithm. Compared with the random library in Java it is about 30% faster and provides better results. Its Period is not as long as the Mersenne Twister's but its still decent.

An implementation can be found here:

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

Edit

It seems that new Variants of XORShift now even beat MerseneTwister and WELL in Quality (not in period though). They pass more empirical quality tests as can be seen in the PRNG Shootout.

They are impressive in performance as well. I did a Benchmark of different implementations in Java, source and results here: https://github.com/tobijdc/PRNG-Performance

Well, the WELL generator is a generalization and improvement of MT-19937.

MT seems to pass your criteria:

It has the colossal period of 2¹⁹⁹³⁷−1 iterations (>43×10^6,000), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and runs faster than other statistically reasonable generators

(From: Wikipedia)

The Mersenne Twister is one of the most extensively tested random number generators in existence. However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes.

(From: Python docs)

And wikipedia has somethings to say about cryptographically secure prng's, if that's your interest.

Besides Mersene Twister and its variants, you can use Salsa20 and its variants (Chacha, and so on..)