14
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Retagged "random-variate" to "random-variable" for consistency with similar questions. $\endgroup$
    – whuber ♦
    Commented Aug 25, 2010 at 14:14

4 Answers 4

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – John D. Cook
    Commented Aug 25, 2010 at 14:53
  • $\begingroup$ 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. $\endgroup$
    – shabbychef
    Commented Aug 25, 2010 at 16:21
  • $\begingroup$ @John Indeed, the polar method is available in R, see the setRNG package. $\endgroup$
    – chl
    Commented Aug 25, 2010 at 21:28
  • $\begingroup$ @John it turns out the Box-Muller method is more sensitive in the tails to the discreteness of the 32-bit random number stream that goes into it. R switched to inversion several years ago because the quality is better even though it's slower. $\endgroup$
    – Thomas Lumley
    Commented Jul 3 at 4:07
8
$\begingroup$

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

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

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Would this be good for implementing on GPUs? Link to details, references? $\endgroup$
    – DarenW
    Commented Aug 2, 2010 at 0:27
  • 3
    $\begingroup$ 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. $\endgroup$
    – brotchie
    Commented Aug 9, 2010 at 1:12
  • 1
    $\begingroup$ Maybe also L'Ecuyer's RNG with multiple streams (j.mp/bzJSlm)? $\endgroup$
    – chl
    Commented Aug 25, 2010 at 21:08
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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