12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Retagged "random-variate" to "random-variable" for consistency with similar questions. $\endgroup$ – whuber Aug 25 '10 at 14:14
10
$\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.

$\endgroup$
  • $\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 Aug 25 '10 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 Aug 25 '10 at 16:21
  • $\begingroup$ @John Indeed, the polar method is available in R, see the setRNG package. $\endgroup$ – chl Aug 25 '10 at 21:28
5
$\begingroup$

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

$\endgroup$
3
$\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.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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