# Pseudo-random number generation algorithms

What algorithms are used in modern and good-quality random number generators?

-
You may see the wikipedia article: en.wikipedia.org/wiki/Random_number_generators – AgCl Jun 25 '10 at 11:36
For algorithms, see en.wikipedia.org/wiki/Pseudorandom_number_generator – lhf Jun 25 '10 at 11:55

Don't miss this wonderful post by Marsaglia. He's not a fan of the Mersenne Twister and offers some strong PRNGs with exceptionally small code footprints. One of his examples is:

static unsigned long
x=123456789,y=362436069,z=521288629,w=88675123,v=886756453;
/* replace defaults with five random seed values in calling program */
unsigned long xorshift(void)
{unsigned long t;
t=(x^(x>>7)); x=y; y=z; z=w; w=v;
v=(v^(v<<6))^(t^(t<<13)); return (y+y+1)*v;}

-

My favorite is Mersenne twister. Excellent quality and very fast.

You can find lots of implements in: http://en.wikipedia.org/wiki/Mersenne_twister

-

Blum-Blum-Shub was the first (and still most popular) provably-secure PRNG (assuming only QRP), despite being incredibly simple. It's very slow compared to non-secure PRNGs, though.

-

I would recommend looking at the paper associated with TestU01:

This has some good info on modern PRNG algorithms, as well as a comparison using a very rigorous test suite called Big Crush. Many common PRNG's fail, but there are a few simpler examples that pass. Notably, the Mersenne twister fails some tests--though this is probably irrelevant for most work unless you are actually looking for linear relations on the output bits.

Some good GPL code is available here, implementing Mersenne twister variants and "mother-of-all" (which does pass Big Crush):

http://www.agner.org/random/

-

P. L'Ecuyer at the University of Montreal is considered one of the world's experts on random generators. You can Google him and find out what he has to say.

-

Many LCGs are still used simply because they are built in to main libraries and have become the de facto standard. They produce terrible output, and do not scale well with state size.

Increasingly MT19937 ("The Mersenne Twister") is replacing LCGs as the most popular RNG. Why this should be is not clear to me, as MT19937 is a mediocre algorithm distinguished by the mathematical proofs about it. It offers provable lack of short term correlation and provable very long period. It is a step up from LCGs, failing only the most stringent of statistical tests. The basic algorithm used is terrible, but the combination of large state size and output hashing ("tempering") allows it to rise to the level of kinda-decent.

I am particularly fond of ISAAC (and it's cousin IBAA) as a high quality RNG of decent speed, with the added bonus of suitability for use in cryptographic applications. They do have a large state size though, almost as large as MT19937. ISAAC is semi-popular - a lot more obscure than MT19937, but still among the better known non-LCG RNGs.

The L'Ecuyer TestU01 paper mentioned in an earlier reply is a good place to find a long list of decent RNGs. It includes a list of many semi-popular RNGs with each RNGs speed and result on the SmallCrush / Crush / BigCrush suite of statistical tests. So, if you just look through the list for every RNG that passes BigCrush and is reasonably fast, that's a list of okay RNGs right there. Some of the RNGs listed, particularly the slower ones, are of more interest to mathematicians analyzing RNGs than to developers who might need to actually use them.

Note that passing all statistical tests is not a very high bar. There are a variety of fast simple RNGs with small states that pass all statistical tests, most of which rarely get used or even mentioned.

-

By far the most popular PRNG in wild is the Mersenne Twister, which is the default RNG for Python, Ruby, PHP, MATLAB, the GSL, and C++11. You'd have to be looking in research papers about RNGs specifically, or in a project concerned with testing RNGs to really find anything else.

-