File: Other-random-number-generators.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (403 lines) | stat: -rw-r--r-- 16,344 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Other random number generators</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Other random number generators">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Other random number generators">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Random-Number-Generation.html#Random-Number-Generation" rel="up" title="Random Number Generation">
<link href="Random-Number-Generator-Performance.html#Random-Number-Generator-Performance" rel="next" title="Random Number Generator Performance">
<link href="Unix-random-number-generators.html#Unix-random-number-generators" rel="previous" title="Unix random number generators">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Other-random-number-generators"></a>
<div class="header">
<p>
Next: <a href="Random-Number-Generator-Performance.html#Random-Number-Generator-Performance" accesskey="n" rel="next">Random Number Generator Performance</a>, Previous: <a href="Unix-random-number-generators.html#Unix-random-number-generators" accesskey="p" rel="previous">Unix random number generators</a>, Up: <a href="Random-Number-Generation.html#Random-Number-Generation" accesskey="u" rel="up">Random Number Generation</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Other-random-number-generators-1"></a>
<h3 class="section">18.11 Other random number generators</h3>

<p>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.
</p>
<p>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, 
<em>2^31</em> or 
<em>2^32</em>).  This
leads to periodicity in the least significant bits of each number,
with only the higher bits having any randomness.  Thus if you want to
produce a random bitstream it is best to avoid using the least
significant bits.
</p>
<dl>
<dt><a name="index-gsl_005frng_005franf"></a>Generator: <strong>gsl_rng_ranf</strong></dt>
<dd><a name="index-RANF-random-number-generator"></a>
<a name="index-CRAY-random-number-generator_002c-RANF"></a>
<p>This is the CRAY random number generator <code>RANF</code>.  Its sequence is
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n) mod m
</pre></div>

<p>defined on 48-bit unsigned integers with <em>a = 44485709377909</em> and
<em>m = 2^48</em>.  The seed specifies the lower
32 bits of the initial value, 
<em>x_1</em>, with the lowest bit set to
prevent the seed taking an even value.  The upper 16 bits of 
<em>x_1</em>
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.
</p>
<p>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.
</p>
<p>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 <em>a</em> mod <em>m</em>.  This is done for compatibility with
the original CRAY implementation.
</p>
<p>Note that you can only seed the generator with integers up to
<em>2^32</em>, while the original CRAY implementation uses
non-portable wide integers which can cover all 
<em>2^48</em> states of the generator.
</p>
<p>The function <code>gsl_rng_get</code> returns the upper 32 bits from each term
of the sequence.  The function <code>gsl_rng_uniform</code> uses the full 48
bits to return the double precision number <em>x_n/m</em>.
</p>
<p>The period of this generator is <em>2^46</em>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005franmar"></a>Generator: <strong>gsl_rng_ranmar</strong></dt>
<dd><a name="index-RANMAR-random-number-generator"></a>
<p>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.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005fr250"></a>Generator: <strong>gsl_rng_r250</strong></dt>
<dd><a name="index-shift_002dregister-random-number-generator"></a>
<a name="index-R250-shift_002dregister-random-number-generator"></a>
<p>This is the shift-register generator of Kirkpatrick and Stoll.  The
sequence is based on the recurrence
</p>
<div class="example">
<pre class="example">x_n = x_{n-103} ^^ x_{n-250}
</pre></div>

<p>where 
<em>^^</em> denotes &ldquo;exclusive-or&rdquo;, defined on
32-bit words.  The period of this generator is about <em>2^250</em> and it
uses 250 words of state per generator.
</p>
<p>For more information see,
</p><ul class="no-bullet">
<li><!-- /@w --> S. Kirkpatrick and E. Stoll, &ldquo;A very fast shift-register sequence random
number generator&rdquo;, <cite>Journal of Computational Physics</cite>, 40, 517&ndash;526
(1981)
</li></ul>
</dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005ftt800"></a>Generator: <strong>gsl_rng_tt800</strong></dt>
<dd><a name="index-TT800-random-number-generator"></a>
<p>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 
<em>2^800</em> and uses 33 words of storage
per generator.
</p>
<p>For more information see,
</p><ul class="no-bullet">
<li><!-- /@w --> Makoto Matsumoto and Yoshiharu Kurita, &ldquo;Twisted GFSR Generators
II&rdquo;, <cite>ACM Transactions on Modelling and Computer Simulation</cite>,
Vol. 4, No. 3, 1994, pages 254&ndash;266.
</li></ul>
</dd></dl>


<dl>
<dt><a name="index-gsl_005frng_005fvax"></a>Generator: <strong>gsl_rng_vax</strong></dt>
<dd><a name="index-VAX-random-number-generator"></a>
<p>This is the VAX generator <code>MTH$RANDOM</code>.  Its sequence is,
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n + c) mod m
</pre></div>

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

<dl>
<dt><a name="index-gsl_005frng_005ftransputer"></a>Generator: <strong>gsl_rng_transputer</strong></dt>
<dd><p>This is the random number generator from the INMOS Transputer
Development system.  Its sequence is,
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n) mod m
</pre></div>

<p>with <em>a = 1664525</em> and 
<em>m = 2^32</em>.
The seed specifies the initial value, 
<em>x_1</em>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005frandu"></a>Generator: <strong>gsl_rng_randu</strong></dt>
<dd><a name="index-RANDU-random-number-generator"></a>
<p>This is the IBM <code>RANDU</code> generator.  Its sequence is
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n) mod m
</pre></div>

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

<dl>
<dt><a name="index-gsl_005frng_005fminstd"></a>Generator: <strong>gsl_rng_minstd</strong></dt>
<dd><a name="index-RANMAR-random-number-generator-1"></a>
<p>This is Park and Miller&rsquo;s &ldquo;minimal standard&rdquo; <small>MINSTD</small> generator, a
simple linear congruence which takes care to avoid the major pitfalls of
such algorithms.  Its sequence is,
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n) mod m
</pre></div>

<p>with <em>a = 16807</em> and 
<em>m = 2^31 - 1 = 2147483647</em>. 
The seed specifies the initial value, 
<em>x_1</em>.  The period of this
generator is about 
<em>2^31</em>.
</p>
<p>This generator was used in the IMSL Library (subroutine RNUN) and in
MATLAB (the RAND function) in the past.  It is also sometimes known by
the acronym &ldquo;GGL&rdquo; (I&rsquo;m not sure what that stands for).
</p>
<p>For more information see,
</p><ul class="no-bullet">
<li><!-- /@w --> Park and Miller, &ldquo;Random Number Generators: Good ones are hard to find&rdquo;,
<cite>Communications of the ACM</cite>, October 1988, Volume 31, No 10, pages
1192&ndash;1201.
</li></ul>
</dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005funi"></a>Generator: <strong>gsl_rng_uni</strong></dt>
<dt><a name="index-gsl_005frng_005funi32"></a>Generator: <strong>gsl_rng_uni32</strong></dt>
<dd><p>This is a reimplementation of the 16-bit SLATEC random number generator
RUNIF. A generalization of the generator to 32 bits is provided by
<code>gsl_rng_uni32</code>.  The original source code is available from NETLIB.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005fslatec"></a>Generator: <strong>gsl_rng_slatec</strong></dt>
<dd><p>This is the SLATEC random number generator RAND. It is ancient.  The
original source code is available from NETLIB.
</p></dd></dl>


<dl>
<dt><a name="index-gsl_005frng_005fzuf"></a>Generator: <strong>gsl_rng_zuf</strong></dt>
<dd><p>This is the ZUFALL lagged Fibonacci series generator of Peterson.  Its
sequence is,
</p>
<div class="example">
<pre class="example">t = u_{n-273} + u_{n-607}
u_n  = t - floor(t)
</pre></div>

<p>The original source code is available from NETLIB.  For more information
see,
</p><ul class="no-bullet">
<li><!-- /@w --> W. Petersen, &ldquo;Lagged Fibonacci Random Number Generators for the NEC
SX-3&rdquo;, <cite>International Journal of High Speed Computing</cite> (1994).
</li></ul>
</dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005fknuthran2"></a>Generator: <strong>gsl_rng_knuthran2</strong></dt>
<dd><p>This is a second-order multiple recursive generator described by Knuth
in <cite>Seminumerical Algorithms</cite>, 3rd Ed., page 108.  Its sequence is,
</p>
<div class="example">
<pre class="example">x_n = (a_1 x_{n-1} + a_2 x_{n-2}) mod m
</pre></div>

<p>with 
<em>a_1 = 271828183</em>, 
<em>a_2 = 314159269</em>, 
and 
<em>m = 2^31 - 1</em>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005fknuthran2002"></a>Generator: <strong>gsl_rng_knuthran2002</strong></dt>
<dt><a name="index-gsl_005frng_005fknuthran"></a>Generator: <strong>gsl_rng_knuthran</strong></dt>
<dd><p>This is a second-order multiple recursive generator described by Knuth
in <cite>Seminumerical Algorithms</cite>, 3rd Ed., Section 3.6.  Knuth
provides its C code.  The updated routine <code>gsl_rng_knuthran2002</code>
is from the revised 9th printing and corrects some weaknesses in the
earlier version, which is implemented as <code>gsl_rng_knuthran</code>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005fborosh13"></a>Generator: <strong>gsl_rng_borosh13</strong></dt>
<dt><a name="index-gsl_005frng_005ffishman18"></a>Generator: <strong>gsl_rng_fishman18</strong></dt>
<dt><a name="index-gsl_005frng_005ffishman20"></a>Generator: <strong>gsl_rng_fishman20</strong></dt>
<dt><a name="index-gsl_005frng_005flecuyer21"></a>Generator: <strong>gsl_rng_lecuyer21</strong></dt>
<dt><a name="index-gsl_005frng_005fwaterman14"></a>Generator: <strong>gsl_rng_waterman14</strong></dt>
<dd><p>These multiplicative generators are taken from Knuth&rsquo;s
<cite>Seminumerical Algorithms</cite>, 3rd Ed., pages 106&ndash;108. Their sequence
is,
</p>
<div class="example">
<pre class="example">x_{n+1} = (a x_n) mod m
</pre></div>

<p>where the seed specifies the initial value, <em>x_1</em>.
The parameters <em>a</em> and <em>m</em> are as follows,
Borosh-Niederreiter: 
<em>a = 1812433253</em>, <em>m = 2^32</em>,
Fishman18:
<em>a = 62089911</em>,
<em>m = 2^31 - 1</em>,
Fishman20:
<em>a = 48271</em>,
<em>m = 2^31 - 1</em>,
L&rsquo;Ecuyer:
<em>a = 40692</em>,
<em>m = 2^31 - 249</em>,
Waterman:
<em>a = 1566083941</em>,
<em>m = 2^32</em>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005frng_005ffishman2x"></a>Generator: <strong>gsl_rng_fishman2x</strong></dt>
<dd><p>This is the L&rsquo;Ecuyer&ndash;Fishman random number generator. It is taken from
Knuth&rsquo;s <cite>Seminumerical Algorithms</cite>, 3rd Ed., page 108. Its sequence
is,
</p>
<div class="example">
<pre class="example">z_{n+1} = (x_n - y_n) mod m
</pre></div>

<p>with <em>m = 2^31 - 1</em>.
<em>x_n</em> and <em>y_n</em> are given by the <code>fishman20</code> 
and <code>lecuyer21</code> algorithms.
The seed specifies the initial value, 
<em>x_1</em>.
</p>
</dd></dl>


<dl>
<dt><a name="index-gsl_005frng_005fcoveyou"></a>Generator: <strong>gsl_rng_coveyou</strong></dt>
<dd><p>This is the Coveyou random number generator. It is taken from Knuth&rsquo;s
<cite>Seminumerical Algorithms</cite>, 3rd Ed., Section 3.2.2. Its sequence
is,
</p>
<div class="example">
<pre class="example">x_{n+1} = (x_n (x_n + 1)) mod m
</pre></div>

<p>with <em>m = 2^32</em>.
The seed specifies the initial value, 
<em>x_1</em>.
</p></dd></dl>





<hr>
<div class="header">
<p>
Next: <a href="Random-Number-Generator-Performance.html#Random-Number-Generator-Performance" accesskey="n" rel="next">Random Number Generator Performance</a>, Previous: <a href="Unix-random-number-generators.html#Unix-random-number-generators" accesskey="p" rel="previous">Unix random number generators</a>, Up: <a href="Random-Number-Generation.html#Random-Number-Generation" accesskey="u" rel="up">Random Number Generation</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>