Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
12  
You may see the wikipedia article: en.wikipedia.org/wiki/Random_number_generators –  AgCl Jun 25 '10 at 11:36
2  
For algorithms, see en.wikipedia.org/wiki/Pseudorandom_number_generator –  lhf Jun 25 '10 at 11:55

6 Answers 6

up vote 5 down vote accepted

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;} 
share|improve this answer

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

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

share|improve this answer

I would recommend looking at the paper associated with TestU01:

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html (see the "Paper" link on this page)

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/

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.