What algorithms are used in modern and goodquality random number generators?

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:



My favorite is Mersenne twister. Excellent quality and very fast. You can find lots of implements in: http://en.wikipedia.org/wiki/Mersenne_twister 


BlumBlumShub was the first (and still most popular) provablysecure PRNG (assuming only QRP), despite being incredibly simple. It's very slow compared to nonsecure PRNGs, though. 


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 teststhough 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 "motherofall" (which does pass Big Crush): 


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 kindadecent. 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 semipopular  a lot more obscure than MT19937, but still among the better known nonLCG 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 semipopular 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. 

