10
$\begingroup$

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

Improve this question
$\endgroup$
2

8 Answers 8

Reset to default
11
$\begingroup$

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;}
Improve this answer
$\endgroup$
3
  • $\begingroup$ Where could one find justifications / analysis of this algorithm, of a more rigorous kind than "Marsaglia says it's good, and he's a smart guy"? $\endgroup$
    – Nate Eldredge
    Commented Dec 28, 2015 at 19:08
  • $\begingroup$ Also, it should be noted that the context of the post suggests that this code is intended for a system where unsigned long is 32 bits. These days most people are using x86-64 and compilers where unsigned long is 64 bits, so I don't think this code will work as designed. The high 32 bits probably won't "randomize" as one would wish. You'd want to change all the variables to uint32_t. $\endgroup$
    – Nate Eldredge
    Commented Dec 28, 2015 at 19:11
  • $\begingroup$ @NateEldredge The justifications are found in "Xorshift RNGs" (by Marsaglia) and the references given there (all Marsaglia's). The paper also has extensions for $32\times n$ bit generation. $\endgroup$
    – Rodrigo Zepeda
    Commented May 27, 2018 at 22:58
4
$\begingroup$

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

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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/

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

AES in CTR mode is one of the best and fastest CSPRNGs. It provides a great amount of pseudorandomness at a high bandwidth.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .