Talk:List of random number generators

From Wikipedia, the free encyclopedia

here the old text as of 26 Jan 06 datebase dump. Don't just paste it in as it copyvio I guess its GNU FDL for licence. --Salix alba (talk) 13:35, 22 February 2006 (UTC)

---

The following pseudorandom number generators are recommended for use in simulation. They have extremely long periods, low correlation, and pass most statistical tests. The routines described here are part of the GNU Scientific Library.

Contents 1 Generators 1.1 gsl_rng_mt19937 1.2 gsl_rng_ranlxs0, gsl_rng_ranlxs1, gsl_rng_ranlxs2 1.3 gsl_rng_ranlxd1, gsl_rng_ranlxd2 1.4 gsl_rng_ranlux, gsl_rng_ranlux389 1.5 gsl_rng_cmrg 1.6 gsl_rng_mrg 1.7 gsl_rng_taus, gsl_rng_taus2 1.8 gsl_rng_gfsr4 2 Unix random number generators 2.1 gsl_rng_rand 2.2 gsl_rng_random_bsd, gsl_rng_random_libc5, gsl_rng_random_glibc2 2.3 gsl_rng_rand48 3 Other random number generators 3.1 gsl_rng_ranf 3.2 gsl_rng_ranmar 3.3 gsl_rng_r250 3.4 gsl_rng_tt800 3.5 gsl_rng_vax 3.6 gsl_rng_transputer 3.7 gsl_rng_randu 3.8 gsl_rng_minstd 3.9 gsl_rng_uni, gsl_rng_uni32 3.10 gsl_rng_slatec 3.11 gsl_rng_zuf 3.12 gsl_rng_borosh13 3.13 gsl_rng_coveyou 3.14 gsl_rng_fishman18 3.15 gsl_rng_fishman20 3.16 gsl_rng_fishman2x 3.17 gsl_rng_knuthran2 3.18 gsl_rng_knuthran 3.19 gsl_rng_lecuyer21 3.20 gsl_rng_waterman14 3.21 msvc_net_2003 4 Performance

[edit] Generators

[edit] gsl_rng_mt19937

The MT19937 generator of Makoto Matsumoto and Takuji Nishimura is a variant of the twisted generalized feedback shift-register algorithm, and is known as the "Mersenne Twister" generator. It has a Mersenne prime period of 2^19937 - 1 (about 10⁶⁰⁰⁰) and is equidistributed in 623 dimensions. It has passed the Diehard statistical tests. It uses 624 words of state per generator and is comparable in speed to other generators. The original generator used a default seed of 4357 and choosing s equal to zero in gsl_rng_set reproduces this.

For more information see:

Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator". ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1 (Jan. 1998), Pages 3-30

The generator gsl_rng_19937 uses the second revision of the seeding procedure published by the two authors above in 2002. The original seeding procedures could cause spurious artifacts for some seed values. They are still available through the alternate generators gsl_rng_mt19937_1999 and gsl_rng_mt19937_1998.

[edit] gsl_rng_ranlxs0, gsl_rng_ranlxs1, gsl_rng_ranlxs2

The generator ranlxs0 is a second-generation version of the RANLUX algorithm of Lüscher, which produces "luxury random numbers". This generator provides single precision output (24 bits) at three luxury levels ranlxs0, ranlxs1 and ranlxs2. It uses double-precision floating point arithmetic internally and can be significantly faster than the integer version of ranlux, particularly on 64-bit architectures. The period of the generator is about 10^171. The algorithm has mathematically proven properties and can provide truly decorrelated numbers at a known level of randomness. The higher luxury levels provide additional decorrelation between samples as an additional safety margin.

[edit] gsl_rng_ranlxd1, gsl_rng_ranlxd2

These generators produce double precision output (48 bits) from the RANLXS generator. The library provides two luxury levels ranlxd1 and ranlxd2.

[edit] gsl_rng_ranlux, gsl_rng_ranlux389

The ranlux generator is an implementation of the original algorithm developed by Lüscher. It uses a lagged-fibonacci-with-skipping algorithm to produce "luxury random numbers". It is a 24-bit generator, originally designed for single-precision IEEE floating point numbers. This implementation is based on integer arithmetic, while the second-generation versions RANLXS and RANLXD described above provide floating-point implementations which will be faster on many platforms. The period of the generator is about 10^171. The algorithm has mathematically proven properties and it can provide truly decorrelated numbers at a known level of randomness. The default level of decorrelation recommended by Lüscher is provided by gsl_rng_ranlux, while gsl_rng_ranlux389 gives the highest level of randomness, with all 24 bits decorrelated. Both types of generator use 24 words of state per generator.

For more information see:

M. Lüscher, "A portable high-quality random number generator for lattice field theory calculations", Computer Physics Communications, 79 (1994) 100-110.

F. James, "RANLUX: A Fortran implementation of the high-quality pseudo-random number generator of Lüscher", Computer Physics Communications, 79 (1994) 111-114

[edit] gsl_rng_cmrg

This is a combined multiple recursive generator by L'Ecuyer. Its sequence is:

<math>z_n = (x_n - y_n) \pmod{m_1}</math>

where the two underlying generators x_n and y_n are:

<math>x_n = (a_1 x_{n-1} + a_2 x_{n-2} + a_3 x_{n-3}) \pmod{m_1}</math>

<math>y_n = (b_1 y_{n-1} + b_2 y_{n-2} + b_3 y_{n-3}) \pmod{m_2}</math>

with coefficients a₁ = 0, a₂ = 63308, a₃ = -183326, b₁ = 86098, b₂ = 0, b₃ = -539608, and moduli m₁ = 2³¹ - 1 = 2147483647 and m₂ = 2145483479.

The period of this generator is 2²⁰⁵ (about 10⁶¹). It uses 6 words of state per generator. For more information see:

P. L'Ecuyer, "Combined Multiple Recursive Random Number Generators," Operations Research, 44, 5 (1996), 816--822.

[edit] gsl_rng_mrg

This is a fifth-order multiple recursive generator by L'Ecuyer, Blouin and Coutre. Its sequence is:

<math>x_n = (a_1 x_{n-1} + a_5 x_{n-5}) \pmod{m}</math>

with a₁ = 107374182, a₂ = a₃ = a₄ = 0, a₅ = 104480 and m = 2³¹ - 1.

The period of this generator is about 10⁴⁶. It uses 5 words of state per generator. More information can be found in the following paper:

P. L'Ecuyer, F. Blouin, and R. Coutre, "A search for good multiple recursive random number generators", ACM Transactions on Modeling and Computer Simulation 3, 87-98 (1993).

[edit] gsl_rng_taus, gsl_rng_taus2

This is a maximally equidistributed combined Tausworthe generator by L'Ecuyer. The sequence is:

x_n = (s1_n ^^ s2_n ^^ s3_n)

where:

s1_{n+1} = (((s1_n&4294967294)<<12)^^(((s1_n<<13)^^s1_n)>>19))

s2_{n+1} = (((s2_n&4294967288)<< 4)^^(((s2_n<< 2)^^s2_n)>>25))

s3_{n+1} = (((s3_n&4294967280)<<17)^^(((s3_n<< 3)^^s3_n)>>11))

computed modulo 2³². In the formulas above ^^ denotes "exclusive-or". Note that the algorithm relies on the properties of 32-bit unsigned integers and has been implemented using a bitmask of 0xFFFFFFFF to make it work on 64 bit machines.

The period of this generator is 2^88 (about 10^26). It uses 3 words of state per generator. The generator gsl_rng_taus2 uses the same algorithm as gsl_rng_taus but with an improved seeding procedure; because of this, the generator gsl_rng_taus2 should now be used in preference to gsl_rng_taus.

For more information see:

P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe Generators", Mathematics of Computation, 65, 213 (1996), 203--213.

P. L'Ecuyer, "Tables of Maximally Equidistributed Combined LFSR Generators", Mathematics of Computation, 68, 225 (1999), 261--269

[edit] gsl_rng_gfsr4

The gfsr4 generator is like a lagged-fibonacci generator, and produces each number as an xor'd sum of four previous values.

r_n = r_{n-A} ^^ r_{n-B} ^^ r_{n-C} ^^ r_{n-D}

Ziff (ref below) notes that "it is now widely known" that two-tap registers (such as R250, which is described below) have serious flaws, the most obvious one being the three-point correlation that comes from the definition of the generator. Nice mathematical properties can be derived for GFSR's, and numerics bears out the claim that 4-tap GFSR's with appropriately chosen offsets are as random as can be measured, using the author's test.

This implementation uses the values suggested the example on p392 of Ziff's article: A=471, B=1586, C=6988, D=9689.

If the offsets are appropriately chosen (such as the one ones in this implementation), then the sequence is said to be maximal; that means that the period is 2^D - 1, where D is the longest lag. (It is one less than 2^D because it is not permitted to have all zeros in the ra[] array.) For this implementation with D=9689 that works out to about 10²⁹¹⁷.

Note that the implementation of this generator using a 32-bit integer amounts to 32 parallel implementations of one-bit generators. One consequence of this is that the period of this 32-bit generator is the same as for the one-bit generator. Moreover, this independence means that all 32-bit patterns are equally likely, and in particular that 0 is an allowed random value. (We are grateful to Heiko Bauke for clarifying for us these properties of GFSR random number generators.)

For more information see:

Robert M. Ziff, "Four-tap shift-register-sequence random-number generators", Computers in Physics, 12(4), Jul/Aug 1998, pp 385-392.

[edit] Unix random number generators

The standard Unix random number generators rand, random, and rand48, are provided as part of GSL. Although these generators are widely available individually, often they are not all available on the same platform. This makes it difficult to write portable code using them. Note that the generators below do not produce high-quality randomness and are not suitable for work requiring accurate statistics. However, if statistical quantities are not being measured and simple variation is all that is needed, these generators are considered quite acceptable.

[edit] gsl_rng_rand

This is the BSD rand() generator. Its sequence is

<math>x_{n+1} = (a x_n + c) \mod m</math>

with <math>a = 1103515245, c = 12345</math> and <math>m = 2^{31}</math>. The seed specifies the initial value, <math>x_1</math>. The period of this generator is <math>2^{31}</math>, and it uses 1 word of storage per generator.

[edit] gsl_rng_random_bsd, gsl_rng_random_libc5, gsl_rng_random_glibc2

These generators implement the random() family of functions, a set of linear feedback shift register generators originally used in BSD Unix. There are several versions of random() in use today: the original BSD version (e.g. on SunOS4), a libc5 version (found on older GNU/Linux systems) and a glibc2 version. Each version uses a different seeding procedure, and thus produces different sequences.

The original BSD routines accepted a variable length buffer for the generator state, with longer buffers providing higher-quality randomness. The random() function implemented algorithms for buffer lengths of 8, 32, 64, 128 and 256 bytes, and the algorithm with the largest length that would fit into the user-supplied buffer was used. To support these algorithms additional generators are available with the following names,

• gsl_rng_random8_bsd
• gsl_rng_random32_bsd
• gsl_rng_random64_bsd
• gsl_rng_random128_bsd
• gsl_rng_random256_bsd

where the numeric suffix indicates the buffer length. The original BSD random function used a 128-byte default buffer and so gsl_rng_random_bsd has been made equivalent to gsl_rng_random128_bsd. Corresponding versions of the libc5 and glibc2 generators are also available, with the names gsl_rng_random8_libc5, gsl_rng_random8_glibc2, etc.

[edit] gsl_rng_rand48

This is the Unix rand48 generator. Its sequence is:

x_{n+1} = (a x_n + c) mod m

defined on 48-bit unsigned integers with a = 25214903917, c = 11 and m = 2^48. The seed specifies the upper 32 bits of the initial value, x_1, with the lower 16 bits set to 0x330E. The function gsl_rng_get returns the upper 32 bits from each term of the sequence. This does not have a direct parallel in the original rand48 functions, but forcing the result to type long int reproduces the output of mrand48. The function gsl_rng_uniform uses the full 48 bits of internal state to return the double precision number x_n/m, which is equivalent to the function drand48. Note that some versions of the GNU C Library contained a bug in mrand48 function which caused it to produce different results (only the lower 16-bits of the return value were set).

[edit] Other random number generators

The generators in this section are provided for compatibility with existing libraries. If you are converting an existing program to use GSL then you can select these generators to check your new implementation against the original one, using the same random number generator. After verifying that your new program reproduces the original results you can then switch to a higher-quality generator.

Note that most of the generators in this section are based on single linear congruence relations, which are the least sophisticated type of generator. In particular, linear congruences have poor properties when used with a non-prime modulus, as several of these routines do (e.g. with a power of two modulus, 2^31 or 2^32). This leads to periodicity in the least significant bits of each number, with only the higher bits having any randomness. Thus, to produce a random bitstream, it is best to avoid using the least significant bits.

[edit] gsl_rng_ranf

This is the CRAY random number generator RANF. Its sequence is

x_{n+1} = (a x_n) mod m

defined on 48-bit unsigned integers with a = 44485709377909 and m = 2^48. The seed specifies the lower 32 bits of the initial value, x_1, with the lowest bit set to prevent the seed taking an even value. The upper 16 bits of x_1 are set to 0. A consequence of this procedure is that the pairs of seeds 2 and 3, 4 and 5, etc produce the same sequences.

The generator compatible with the CRAY MATHLIB routine RANF. It produces double precision floating point numbers which should be identical to those from the original RANF.

There is a subtlety in the implementation of the seeding. The initial state is reversed through one step, by multiplying by the modular inverse of a mod m. This is done for compatibility with the original CRAY implementation.

Note that you can only seed the generator with integers up to 2^32, while the original CRAY implementation uses non-portable wide integers which can cover all 2^48 states of the generator.

The function gsl_rng_get returns the upper 32 bits from each term of the sequence. The function gsl_rng_uniform uses the full 48 bits to return the double precision number x_n/m.

The period of this generator is 2^46.

[edit] gsl_rng_ranmar

This is the RANMAR lagged-fibonacci generator of Marsaglia, Zaman and Tsang. It is a 24-bit generator, originally designed for single-precision IEEE floating point numbers. It was included in the CERNLIB high-energy physics library.

[edit] gsl_rng_r250

This is the shift-register generator of Kirkpatrick and Stoll. The sequence is

x_n = x_{n-103} ^^ x_{n-250}

where ^^ denote "exclusive-or", defined on 32-bit words. The period of this generator is about 2^250 and it uses 250 words of state per generator.

For more information see:

S. Kirkpatrick and E. Stoll, "A very fast shift-register sequence random number generator", Journal of Computational Physics, 40, 517-526 (1981)

[edit] gsl_rng_tt800

This is an earlier version of the twisted generalized feedback shift-register generator, and has been superseded by the development of MT19937. However, it is still an acceptable generator in its own right. It has a period of 2^800 and uses 33 words of storage per generator.

For more information see:

Makoto Matsumoto and Yoshiharu Kurita, "Twisted GFSR Generators II", ACM Transactions on Modelling and Computer Simulation, Vol. 4, No. 3, 1994, pages 254-266.

[edit] gsl_rng_vax

This is the VAX generator MTH$RANDOM. Its sequence is:

x_{n+1} = (a x_n + c) mod m

with a = 69069, c = 1 and m = 2^32. The seed specifies the initial value, x_1. The period of this generator is 2^32 and it uses 1 word of storage per generator.

[edit] gsl_rng_transputer

This is the random number generator from the INMOS Transputer Development system. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 1664525 and m = 2^32. The seed specifies the initial value, x_1.

[edit] gsl_rng_randu

This is the IBM RANDU generator. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 65539 and m = 2^31. The seed specifies the initial value, x_1. The period of this generator was only 2^29. It has become a textbook example of a poor generator.

[edit] gsl_rng_minstd

This is Park and Miller's "minimal standard" MINSTD generator, a simple linear congruence which takes care to avoid the major pitfalls of such algorithms. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 16807 and m = 2^31 - 1 = 2147483647. The seed specifies the initial value, x_1. The period of this generator is about 2^31.

This generator is used in the IMSL Library (subroutine RNUN) and in MATLAB (the RAND function). It is also sometimes known by the acronym "GGL" (I'm not sure what that stands for).

For more information see:

Park and Miller, "Random Number Generators: Good ones are hard to find", Communications of the ACM, October 1988, Volume 31, No 10, pages 1192-1201.

[edit] gsl_rng_uni, gsl_rng_uni32

This is a reimplementation of the 16-bit SLATEC random number generator RUNIF. A generalization of the generator to 32 bits is provided by gsl_rng_uni32. The original source code is available from NETLIB.

[edit] gsl_rng_slatec

This is the SLATEC random number generator RAND. It is ancient. The original source code is available froim NETLIB.

[edit] gsl_rng_zuf

This is the ZUFALL lagged Fibonacci series generator of Peterson. Its sequence is:

t = u_{n-273} + u_{n-607} u_n = t - floor(t)

The original source code is available from NETLIB. For more information see:

W. Petersen, "Lagged Fibonacci Random Number Generators for the NEC SX-3", International Journal of High Speed Computing (1994).

[edit] gsl_rng_borosh13

This is the Borosh, Niederreiter random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., pages 106-108. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 1812433253 and m = 2^32. The seed specifies the initial value, x_1.

[edit] gsl_rng_coveyou

This is the Coveyou random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., Section 3.2.2. Its sequence is:

x_{n+1} = (x_n (x_n + 1)) mod m

with m = 2^32. The seed specifies the initial value, x_1.

[edit] gsl_rng_fishman18

This is the Fishman, Moore III random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., pages 106-108. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 62089911 and m = 2^31 - 1. The seed specifies the initial value, x_1.

[edit] gsl_rng_fishman20

This is the Fishman random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., page 108. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 48271 and m = 2^31 - 1. The seed specifies the initial value, x_1.

[edit] gsl_rng_fishman2x

This is the L'Ecuyer--Fishman random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., page 108. Its sequence is:

z_{n+1} = (x_n - y_n) mod m

with m = 2^31 - 1. x_n and y_n are given by the fishman20 and lecuyer21 algorithms. The seed specifies the initial value, x_1.

[edit] gsl_rng_knuthran2

This is a second-order multiple recursive generator described by Knuth in Seminumerical Algorithms, 3rd Ed., page 108. Its sequence is:

x_n = (a_1 x_{n-1} + a_2 x_{n-2}) mod m

with a_1 = 271828183, a_2 = 314159269, and m = 2^31 - 1.

[edit] gsl_rng_knuthran

This is a second-order multiple recursive generator described by Knuth in Seminumerical Algorithms, 3rd Ed., Section 3.6. Knuth provides its C code.

[edit] gsl_rng_lecuyer21

This is the L'Ecuyer random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., page 106-108. Its sequence is,

x_{n+1} = (a x_n) mod m

with a = 40692 and m = 2^31 - 249. The seed specifies the initial value, x_1.

[edit] gsl_rng_waterman14

This is the Waterman random number generator. It is taken from Knuth's Seminumerical Algorithms, 3rd Ed., page 106-108. Its sequence is:

x_{n+1} = (a x_n) mod m

with a = 1566083941 and m = 2^32. The seed specifies the initial value, x_1.

[edit] msvc_net_2003

Microsoft Visual C++ (.net, version 2003) uses the following function for rand():

seed = seed * 214013L + 2531011L;<br> x_{n+1} = (seed >> 16) & 0x7fff;

seed is a 32-bit number and is initialized to 1.

[edit] Performance

The following table shows the relative performance of some of the random number generators. The fastest simulation quality generators are taus, gfsr4 and mt19937.

1754 k ints/sec,    870 k doubles/sec, taus
1613 k ints/sec,    855 k doubles/sec, gfsr4
1370 k ints/sec,    769 k doubles/sec, mt19937
 565 k ints/sec,    571 k doubles/sec, ranlxs0
 400 k ints/sec,    405 k doubles/sec, ranlxs1
 490 k ints/sec,    389 k doubles/sec, mrg
 407 k ints/sec,    297 k doubles/sec, ranlux
 243 k ints/sec,    254 k doubles/sec, ranlxd1
 251 k ints/sec,    253 k doubles/sec, ranlxs2
 238 k ints/sec,    215 k doubles/sec, cmrg
 247 k ints/sec,    198 k doubles/sec, ranlux389
 141 k ints/sec,    140 k doubles/sec, ranlxd2

1852 k ints/sec,    935 k doubles/sec, ran3
 813 k ints/sec,    575 k doubles/sec, ran0
 787 k ints/sec,    476 k doubles/sec, ran1
 379 k ints/sec,    292 k doubles/sec, ran2

---

Originally based on an entry in the GNU Scientific Library manual. Used under the GNU FDL.

---