What is the best pseudo-random number generator as of today? [closed]

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?

Trilbee

What specific statistical tests do you want it to pass? There is no such thing as passing all statistical tests... – Sing

I agree that it may not pass all statistical tests. But my question is simple - which is the best PRNG (time and complexity of algorithm is not an issue) – Trilbee

Most systems/languages have a Cryptographically secure PRNG (CSPRNG), use it. – Spool

Answer 1

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.

Apodaca

How does SFMT compare with WELL prng? – Trilbee

This is generally wrong. You need to take into account the whole parameters: WELL has a better equidistribution property but is also far slower (about five times as slow indeed) than SFMT. Moreover, following your last criterion, WELL generators do not display the same overwhelming periods as SFMT: up to 2^44497 for well when SFMT proposes 2^216091. You can find these figures in the original SFMT publication. Be careful to consider the application and the PRNG as a whole when you have to decide which PRNG to use. math.sci.hiroshima-u.ac.jp/~saito/articles/sfmt.pdf – Apodaca

I agree. you've answered my question. – Trilbee

Answer 2

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.

Ambler

Note: for xoroshiro128+ (and some others in that family), the least significant bit is apparently of fairly low quality, beware. The paper for PCG has not been accepted by ACM Transactions on Mathematical Software (TOMS), but that was apparently more due to style and length. At any rate, I'm not a PRNG researcher myself, the above is just the distillate of my meta-research on what to use - proceed at your own risk... – Ambler

you didn't mention SFMT and Well mentioned in jopasserat's answer. is that these two already fall into the items you listed, or they are now not really considered state of the art anymore ? – Wolgast

@athos: See the PRNG Shootout at Vigna's page linked above (xoshiro.di.unimi.it). It appears that SFMT and WELL fail some BigCrush tests, SFMT uses wastefully much state, and WELL is relatively slow. – Ambler

Answer 3

1. 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.

2. 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.

3. 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)

Spirometer

can a 32-bit version of the PRNG be made while still passing the test? for example, using a seedstate of two uint32_t integers. – Burtburta

For 32 bit: Change the 12 to 9, the 25 to 21 (both times it appears), the 64 to 32, and the integer types (the state variables, the local variable, and the return type) to whatever 32 bit integer type name you want to use. Leave the 3 as-is. You can use all three of rng_a, rng_b, and rng_c for seeding without problem. It passes all tests I know of. Note that the provable minimum period drops to 2^32, the average period drops to 2^127, and the statespace drops to 2^128. – Spirometer

Thank you for the 32-bit changes, looks great. So the 128-bit state is a+b+c+rng_counter? Can the seed() procedure be skipped and instead use Murmur/Spooky hash to seed the full state, with rng_counter wrapping over? Or is the setup in seed() pertinent to its quality. That is, does rng_counter have to be 1, and a,b,c have to be equal. I noticed a similar seeding procedure used in Jenkins' smallprng. – Burtburta

Answer length constrained. Yes, you can seed from a hasher, and doing so obviates the need to skip the first few outputs. Yes, you can seed to (counter) in addition to (a,b,c). However, each of those comes with caveats about your ability to guarantee unique output. If you seed from a hasher, with 2^64 distinct inputs to the hasher you have a fair chance of finding 2 that produce the same (a,b,c,counter) value. And likewise when seeding to counter to there's a (tiny) risk of having two seedings outputs overlap. Doesn't matter in normal applications, but in exotic cases it could matter. – Spirometer

Answer 4

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

Courtund

what makes xorshift good? its almost too simple. even the latest of the variants, xoshiro, still has issues with LinearComp/MatrixRank tests in TestU01. PCG's author also criticizes it for its 'zeroland' issue. – Burtburta

To be honest, I wrote the author of PCG some questions and was not really satisfied with her answers. Furthermore her work has been quite criticized. However it as been years, so I don't remember the details. PCG is now also part of the linked PRNG Shootout comparison. – Courtund

"The dread of criticism is the death of genius". Both PCG and xo(ro)shiro have their issues (and biases). Personally I like the more obscure generators: sfc64, v3b, mulberry32 (for embedded systems). Xoshiro is essentially a big improvement over Xorshift (2003) yet they both suffer from LFSR issues. At some point, a PRNG works fine for everyone except academia. – Burtburta

Answer 5

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

Mousetail

Answer 6

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.

Combust

Yes, MT does satisfy all those criteria. So is there any PRNG better than MT? – Trilbee

It need not be cryptographically secure. – Trilbee

Answer 7

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

Ericaericaceous