# Pseudo-random number generation algorithms

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

• Retagged "random-variate" to "random-variable" for consistency with similar questions. – whuber Aug 25 '10 at 14:14

In R, the default setting for random number generation are:

1. For U(0,1), use the Mersenne-Twister algorithm
2. For Guassian numbers use the numerical inversion of the standard normal distribution function.

You can easily check this, viz.

> RNGkind()
[1] "Mersenne-Twister" "Inversion"


It is possible to change the default generator to other PRNGs, such as Super-Duper,Wichmann-Hill, Marsaglia-Multicarry or even a user-supplied PRNG. See the ?RNGkind for further details. I have never needed to change the default PRNG.

The C GSL library also uses the Mersenne-Twister by default.

• Are you sure about your second point, generating normal random variables by inverting the CDF? The inverse of the normal CDF is a fairly expensive function to evaluate. I imagine Box-Muller's method would be faster. Faster still would be Marsaglia's ziggurat method for generating normals. – John D. Cook Aug 25 '10 at 14:53
• I also find this suspicious. Marsaglia's Ziggurat is the default in Matlab, and I can't imagine Matlab being better than R in the field of random number generation. – shabbychef Aug 25 '10 at 16:21
• @John Indeed, the polar method is available in R, see the setRNG package. – chl Aug 25 '10 at 21:28

The Mersenne Twister is one I've come across and used before now.

The Xorshift PNG designed by George Marsaglia. Its period (2^128-1) is much shorter than the Mersenne-Twister but the algorithm is very simple to implement and lends itself to parallelization. Performs well on many-core architectures such as DSP chips and Nvidia's Tesla.

• Would this be good for implementing on GPUs? Link to details, references? – DarenW Aug 2 '10 at 0:27
• Thomas, Howes, Luk - 2009 - A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation. doi.acm.org/10.1145/1508128.1508139. Discussion + benchmarks of a set of PNGs executing on CPU, GPU, FPGA and Massively Parallel Processor Arrays. – brotchie Aug 9 '10 at 1:12
• Maybe also L'Ecuyer's RNG with multiple streams (j.mp/bzJSlm)? – chl Aug 25 '10 at 21:08

At http://prng.di.unimi.it/ you can find a shootout of several random number generators tested using TestU01, the modern test suite for pseudorandom number generators that replaced diehard and dieharder. You can pick and choose.