3
<title>Random number generator algorithms - GNU Scientific Library -- Reference Manual</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="GNU Scientific Library -- Reference Manual">
6
<meta name="generator" content="makeinfo 4.8">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Random-Number-Generation.html#Random-Number-Generation" title="Random Number Generation">
9
<link rel="prev" href="Reading-and-writing-random-number-generator-state.html#Reading-and-writing-random-number-generator-state" title="Reading and writing random number generator state">
10
<link rel="next" href="Unix-random-number-generators.html#Unix-random-number-generators" title="Unix random number generators">
11
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
13
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 The GSL Team.
15
Permission is granted to copy, distribute and/or modify this document
16
under the terms of the GNU Free Documentation License, Version 1.2 or
17
any later version published by the Free Software Foundation; with the
18
Invariant Sections being ``GNU General Public License'' and ``Free Software
19
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
20
and with the Back-Cover Text being (a) (see below). A copy of the
21
license is included in the section entitled ``GNU Free Documentation
24
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
25
GNU Manual, like GNU software.''-->
26
<meta http-equiv="Content-Style-Type" content="text/css">
27
<style type="text/css"><!--
28
pre.display { font-family:inherit }
29
pre.format { font-family:inherit }
30
pre.smalldisplay { font-family:inherit; font-size:smaller }
31
pre.smallformat { font-family:inherit; font-size:smaller }
32
pre.smallexample { font-size:smaller }
33
pre.smalllisp { font-size:smaller }
34
span.sc { font-variant:small-caps }
35
span.roman { font-family:serif; font-weight:normal; }
36
span.sansserif { font-family:sans-serif; font-weight:normal; }
42
<a name="Random-number-generator-algorithms"></a>
43
Next: <a rel="next" accesskey="n" href="Unix-random-number-generators.html#Unix-random-number-generators">Unix random number generators</a>,
44
Previous: <a rel="previous" accesskey="p" href="Reading-and-writing-random-number-generator-state.html#Reading-and-writing-random-number-generator-state">Reading and writing random number generator state</a>,
45
Up: <a rel="up" accesskey="u" href="Random-Number-Generation.html#Random-Number-Generation">Random Number Generation</a>
49
<h3 class="section">17.9 Random number generator algorithms</h3>
51
<p>The functions described above make no reference to the actual algorithm
52
used. This is deliberate so that you can switch algorithms without
53
having to change any of your application source code. The library
54
provides a large number of generators of different types, including
55
simulation quality generators, generators provided for compatibility
56
with other libraries and historical generators from the past.
58
<p>The following generators are recommended for use in simulation. They
59
have extremely long periods, low correlation and pass most statistical
63
— Generator: <b>gsl_rng_mt19937</b><var><a name="index-gsl_005frng_005fmt19937-1391"></a></var><br>
64
<blockquote><p><a name="index-MT19937-random-number-generator-1392"></a>The MT19937 generator of Makoto Matsumoto and Takuji Nishimura is a
65
variant of the twisted generalized feedback shift-register algorithm,
66
and is known as the “Mersenne Twister” generator. It has a Mersenne
68
<!-- {$2^{19937} - 1$} -->
70
<!-- {$10^{6000}$} -->
72
equi-distributed in 623 dimensions. It has passed the <span class="sc">diehard</span>
73
statistical tests. It uses 624 words of state per generator and is
74
comparable in speed to the other generators. The original generator used
75
a default seed of 4357 and choosing <var>s</var> equal to zero in
76
<code>gsl_rng_set</code> reproduces this.
78
<p>For more information see,
80
<li>Makoto Matsumoto and Takuji Nishimura, “Mersenne Twister: A
81
623-dimensionally equidistributed uniform pseudorandom number
82
generator”. <cite>ACM Transactions on Modeling and Computer
83
Simulation</cite>, Vol. 8, No. 1 (Jan. 1998), Pages 3–30
86
<p class="noindent">The generator <code>gsl_rng_mt19937</code> uses the second revision of the
87
seeding procedure published by the two authors above in 2002. The
88
original seeding procedures could cause spurious artifacts for some seed
89
values. They are still available through the alternative generators
90
<code>gsl_rng_mt19937_1999</code> and <code>gsl_rng_mt19937_1998</code>.
91
</p></blockquote></div>
94
— Generator: <b>gsl_rng_ranlxs0</b><var><a name="index-gsl_005frng_005franlxs0-1393"></a></var><br>
95
— Generator: <b>gsl_rng_ranlxs1</b><var><a name="index-gsl_005frng_005franlxs1-1394"></a></var><br>
96
— Generator: <b>gsl_rng_ranlxs2</b><var><a name="index-gsl_005frng_005franlxs2-1395"></a></var><br>
97
<blockquote><p><a name="index-RANLXS-random-number-generator-1396"></a>
98
The generator <code>ranlxs0</code> is a second-generation version of the
99
<span class="sc">ranlux</span> algorithm of Lüscher, which produces “luxury random
100
numbers”. This generator provides single precision output (24 bits) at
101
three luxury levels <code>ranlxs0</code>, <code>ranlxs1</code> and <code>ranlxs2</code>.
102
It uses double-precision floating point arithmetic internally and can be
103
significantly faster than the integer version of <code>ranlux</code>,
104
particularly on 64-bit architectures. The period of the generator is
105
about <!-- {$10^{171}$} -->
106
10^171. The algorithm has mathematically proven properties and
107
can provide truly decorrelated numbers at a known level of randomness.
108
The higher luxury levels provide increased decorrelation between samples
109
as an additional safety margin.
110
</p></blockquote></div>
113
— Generator: <b>gsl_rng_ranlxd1</b><var><a name="index-gsl_005frng_005franlxd1-1397"></a></var><br>
114
— Generator: <b>gsl_rng_ranlxd2</b><var><a name="index-gsl_005frng_005franlxd2-1398"></a></var><br>
115
<blockquote><p><a name="index-RANLXD-random-number-generator-1399"></a>
116
These generators produce double precision output (48 bits) from the
117
<span class="sc">ranlxs</span> generator. The library provides two luxury levels
118
<code>ranlxd1</code> and <code>ranlxd2</code>.
119
</p></blockquote></div>
122
— Generator: <b>gsl_rng_ranlux</b><var><a name="index-gsl_005frng_005franlux-1400"></a></var><br>
123
— Generator: <b>gsl_rng_ranlux389</b><var><a name="index-gsl_005frng_005franlux389-1401"></a></var><br>
125
<p><a name="index-RANLUX-random-number-generator-1402"></a>The <code>ranlux</code> generator is an implementation of the original
126
algorithm developed by Lüscher. It uses a
127
lagged-fibonacci-with-skipping algorithm to produce “luxury random
128
numbers”. It is a 24-bit generator, originally designed for
129
single-precision IEEE floating point numbers. This implementation is
130
based on integer arithmetic, while the second-generation versions
131
<span class="sc">ranlxs</span> and <span class="sc">ranlxd</span> described above provide floating-point
132
implementations which will be faster on many platforms.
133
The period of the generator is about <!-- {$10^{171}$} -->
134
10^171. The algorithm has mathematically proven properties and
135
it can provide truly decorrelated numbers at a known level of
136
randomness. The default level of decorrelation recommended by Lüscher
137
is provided by <code>gsl_rng_ranlux</code>, while <code>gsl_rng_ranlux389</code>
138
gives the highest level of randomness, with all 24 bits decorrelated.
139
Both types of generator use 24 words of state per generator.
141
<p>For more information see,
143
<li>M. Lüscher, “A portable high-quality random number generator for
144
lattice field theory calculations”, <cite>Computer Physics
145
Communications</cite>, 79 (1994) 100–110.
146
<li>F. James, “RANLUX: A Fortran implementation of the high-quality
147
pseudo-random number generator of Lüscher”, <cite>Computer Physics
148
Communications</cite>, 79 (1994) 111–114
150
</p></blockquote></div>
153
— Generator: <b>gsl_rng_cmrg</b><var><a name="index-gsl_005frng_005fcmrg-1403"></a></var><br>
154
<blockquote><p><a name="index-CMRG_002c-combined-multiple-recursive-random-number-generator-1404"></a>This is a combined multiple recursive generator by L'Ecuyer.
156
where the two underlying generators x_n and y_n are,
165
<!-- {$m_1 = 2^{31} - 1 = 2147483647$} -->
166
m_1 = 2^31 - 1 = 2147483647
168
<!-- {$m_2 = 2145483479$} -->
171
<p>The period of this generator is
172
<!-- {$\hbox{lcm}(m_1^3-1, m_2^3-1)$} -->
173
lcm(m_1^3-1, m_2^3-1),
174
which is approximately
180
6 words of state per generator. For more information see,
183
<li>P. L'Ecuyer, “Combined Multiple Recursive Random Number
184
Generators”, <cite>Operations Research</cite>, 44, 5 (1996), 816–822.
186
</p></blockquote></div>
189
— Generator: <b>gsl_rng_mrg</b><var><a name="index-gsl_005frng_005fmrg-1405"></a></var><br>
190
<blockquote><p><a name="index-MRG_002c-multiple-recursive-random-number-generator-1406"></a>This is a fifth-order multiple recursive generator by L'Ecuyer, Blouin
191
and Coutre. Its sequence is,
197
<!-- {$m = 2^{31}-1$} -->
200
<p>The period of this generator is about
202
10^46. It uses 5 words
203
of state per generator. More information can be found in the following
206
<li>P. L'Ecuyer, F. Blouin, and R. Coutre, “A search for good multiple
207
recursive random number generators”, <cite>ACM Transactions on Modeling and
208
Computer Simulation</cite> 3, 87–98 (1993).
210
</p></blockquote></div>
213
— Generator: <b>gsl_rng_taus</b><var><a name="index-gsl_005frng_005ftaus-1407"></a></var><br>
214
— Generator: <b>gsl_rng_taus2</b><var><a name="index-gsl_005frng_005ftaus2-1408"></a></var><br>
215
<blockquote><p><a name="index-Tausworthe-random-number-generator-1409"></a>This is a maximally equidistributed combined Tausworthe generator by
216
L'Ecuyer. The sequence is,
220
2^32. In the formulas above
223
denotes “exclusive-or”. Note that the algorithm relies on the properties
224
of 32-bit unsigned integers and has been implemented using a bitmask
225
of <code>0xFFFFFFFF</code> to make it work on 64 bit machines.
227
<p>The period of this generator is <!-- {$2^{88}$} -->
230
10^26). It uses 3 words of state per generator. For more
234
<li>P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe
235
Generators”, <cite>Mathematics of Computation</cite>, 65, 213 (1996), 203–213.
238
<p class="noindent">The generator <code>gsl_rng_taus2</code> uses the same algorithm as
239
<code>gsl_rng_taus</code> but with an improved seeding procedure described in
243
<li>P. L'Ecuyer, “Tables of Maximally Equidistributed Combined LFSR
244
Generators”, <cite>Mathematics of Computation</cite>, 68, 225 (1999), 261–269
247
<p class="noindent">The generator <code>gsl_rng_taus2</code> should now be used in preference to
248
<code>gsl_rng_taus</code>.
249
</p></blockquote></div>
252
— Generator: <b>gsl_rng_gfsr4</b><var><a name="index-gsl_005frng_005fgfsr4-1410"></a></var><br>
253
<blockquote><p><a name="index-Four_002dtap-Generalized-Feedback-Shift-Register-1411"></a>The <code>gfsr4</code> generator is like a lagged-fibonacci generator, and
254
produces each number as an <code>xor</code>'d sum of four previous values.
256
<p>Ziff (ref below) notes that “it is now widely known” that two-tap
257
registers (such as R250, which is described below)
258
have serious flaws, the most obvious one being the three-point
259
correlation that comes from the definition of the generator. Nice
260
mathematical properties can be derived for GFSR's, and numerics bears
261
out the claim that 4-tap GFSR's with appropriately chosen offsets are as
262
random as can be measured, using the author's test.
264
<p>This implementation uses the values suggested the example on p392 of
265
Ziff's article: A=471, B=1586, C=6988, D=9689.
267
<p>If the offsets are appropriately chosen (such as the one ones in this
268
implementation), then the sequence is said to be maximal; that means
269
that the period is 2^D - 1, where D is the longest lag.
270
(It is one less than 2^D because it is not permitted to have all
271
zeros in the <code>ra[]</code> array.) For this implementation with
272
D=9689 that works out to about <!-- {$10^{2917}$} -->
275
<p>Note that the implementation of this generator using a 32-bit
276
integer amounts to 32 parallel implementations of one-bit
277
generators. One consequence of this is that the period of this
278
32-bit generator is the same as for the one-bit generator.
279
Moreover, this independence means that all 32-bit patterns are
280
equally likely, and in particular that 0 is an allowed random
281
value. (We are grateful to Heiko Bauke for clarifying for us these
282
properties of GFSR random number generators.)
284
<p>For more information see,
286
<li>Robert M. Ziff, “Four-tap shift-register-sequence random-number
287
generators”, <cite>Computers in Physics</cite>, 12(4), Jul/Aug
288
1998, pp 385–392.
290
</p></blockquote></div>
added
removed
Random-number-generator-algorithms.html
