rng.texi

来自「math library from gnu」· TEXI 代码 · 共 1,466 行 · 第 1/4 页

@ifinfo

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

@end ifinfo
@noindent
with @math{a = 16807} and 
@c{$m = 2^{31} - 1 = 2147483647$}
@math{m = 2^31 - 1 = 2147483647}. 
The seed specifies the initial value, 
@c{$x_1$}
@math{x_1}.  The period of this
generator is about 
@c{$2^{31}$}
@math{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,
@itemize @asis
@item
Park and Miller, ``Random Number Generators: Good ones are hard to find'',
@cite{Communications of the ACM}, October 1988, Volume 31, No 10, pages
1192--1201.
@end itemize
@end deffn

@deffn {Generator} gsl_rng_uni
@deffnx {Generator} 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
@code{gsl_rng_uni32}.  The original source code is available from NETLIB.
@end deffn

@deffn {Generator} gsl_rng_slatec
This is the SLATEC random number generator RAND. It is ancient.  The
original source code is available from NETLIB.
@end deffn


@deffn {Generator} gsl_rng_zuf
This is the ZUFALL lagged Fibonacci series generator of Peterson.  Its
sequence is,
@tex
\beforedisplay
$$ 
\eqalign{
t &= u_{n-273} + u_{n-607} \cr
u_n  &= t - \hbox{floor}(t)
}
$$
\afterdisplay
@end tex
@ifinfo

@example
t = u_@{n-273@} + u_@{n-607@}
u_n  = t - floor(t)
@end example
@end ifinfo

The original source code is available from NETLIB.  For more information
see,
@itemize @asis
@item
W. Petersen, ``Lagged Fibonacci Random Number Generators for the NEC
SX-3'', @cite{International Journal of High Speed Computing} (1994).
@end itemize
@end deffn

@deffn {Generator} gsl_rng_knuthran2
This is a second-order multiple recursive generator described by Knuth
in @cite{Seminumerical Algorithms}, 3rd Ed., page 108.  Its sequence is,
@tex
\beforedisplay
$$
x_n = (a_1 x_{n-1} + a_2 x_{n-2}) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo

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

@end ifinfo
@noindent
with 
@math{a_1 = 271828183}, 
@math{a_2 = 314159269}, 
and 
@c{$m = 2^{31}-1$}
@math{m = 2^31 - 1}.
@end deffn

@deffn {Generator} gsl_rng_knuthran2002
@deffnx {Generator} gsl_rng_knuthran
This is a second-order multiple recursive generator described by Knuth
in @cite{Seminumerical Algorithms}, 3rd Ed., Section 3.6.  Knuth
provides its C code.  The updated routine @code{gsl_rng_knuthran2002}
is from the revised 9th printing and corrects some weaknesses in the
earlier version, which is implemented as @code{gsl_rng_knuthran}.
@end deffn

@deffn {Generator} gsl_rng_borosh13
@deffnx {Generator} gsl_rng_fishman18
@deffnx {Generator} gsl_rng_fishman20
@deffnx {Generator} gsl_rng_lecuyer21
@deffnx {Generator} gsl_rng_waterman14
These multiplicative generators are taken from Knuth's
@cite{Seminumerical Algorithms}, 3rd Ed., pages 106--108. Their sequence
is,
@tex
\beforedisplay
$$
x_{n+1} = (a x_n) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo

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

@end ifinfo
@noindent
where the seed specifies the initial value, @c{$x_1$}
@math{x_1}.
The parameters @math{a} and @math{m} are as follows,
Borosh-Niederreiter: 
@math{a = 1812433253}, @c{$m = 2^{32}$}
@math{m = 2^32},
Fishman18:
@math{a = 62089911},
@c{$m = 2^{31}-1$}
@math{m = 2^31 - 1},
Fishman20:
@math{a = 48271},
@c{$m = 2^{31}-1$}
@math{m = 2^31 - 1},
L'Ecuyer:
@math{a = 40692},
@c{$m = 2^{31}-249$}
@math{m = 2^31 - 249},
Waterman:
@math{a = 1566083941},
@c{$m = 2^{32}$}
@math{m = 2^32}.
@end deffn

@deffn {Generator} gsl_rng_fishman2x
This is the L'Ecuyer--Fishman random number generator. It is taken from
Knuth's @cite{Seminumerical Algorithms}, 3rd Ed., page 108. Its sequence
is,
@tex
\beforedisplay
$$
z_{n+1} = (x_n - y_n) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo

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

@end ifinfo
@noindent
with @c{$m = 2^{31}-1$}
@math{m = 2^31 - 1}.
@math{x_n} and @math{y_n} are given by the @code{fishman20} 
and @code{lecuyer21} algorithms.
The seed specifies the initial value, 
@c{$x_1$}
@math{x_1}.

@end deffn


@deffn {Generator} gsl_rng_coveyou
This is the Coveyou random number generator. It is taken from Knuth's
@cite{Seminumerical Algorithms}, 3rd Ed., Section 3.2.2. Its sequence
is,
@tex
\beforedisplay
$$
x_{n+1} = (x_n (x_n + 1)) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo

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

@end ifinfo
@noindent
with @c{$m = 2^{32}$}
@math{m = 2^32}.
The seed specifies the initial value, 
@c{$x_1$}
@math{x_1}.
@end deffn





@node Random Number Generator Performance
@section Performance

@comment
@comment I made the original plot like this
@comment ./benchmark > tmp; cat tmp | perl -n -e '($n,$s) = split(" ",$_); printf("%17s ",$n); print "-" x ($s/1e5), "\n";'
@comment

The following table shows the relative performance of a selection the
available random number generators.  The fastest simulation quality
generators are @code{taus}, @code{gfsr4} and @code{mt19937}.  The
generators which offer the best mathematically-proven quality are those
based on the @sc{ranlux} algorithm.

@comment The large number of generators based on single linear congruences are
@comment represented by the @code{random} generator below.  These generators are
@comment fast but have the lowest statistical quality.

@example
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
@end example

@node Random Number Generator Examples
@section Examples

The following program demonstrates the use of a random number generator
to produce uniform random numbers in the range [0.0, 1.0),

@example
@verbatiminclude examples/rngunif.c
@end example

@noindent
Here is the output of the program,

@example
$ ./a.out 
@verbatiminclude examples/rngunif.out
@end example

@noindent
The numbers depend on the seed used by the generator.  The default seed
can be changed with the @code{GSL_RNG_SEED} environment variable to
produce a different stream of numbers.  The generator itself can be
changed using the environment variable @code{GSL_RNG_TYPE}.  Here is the
output of the program using a seed value of 123 and the
multiple-recursive generator @code{mrg},

@example
$ GSL_RNG_SEED=123 GSL_RNG_TYPE=mrg ./a.out 
@verbatiminclude examples/rngunif.2.out
@end example

@node Random Number References and Further Reading
@section References and Further Reading

The subject of random number generation and testing is reviewed
extensively in Knuth's @cite{Seminumerical Algorithms}.

@itemize @asis
@item
Donald E. Knuth, @cite{The Art of Computer Programming: Seminumerical
Algorithms} (Vol 2, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896842.
@end itemize

@noindent
Further information is available in the review paper written by Pierre
L'Ecuyer,

@itemize @asis
P. L'Ecuyer, ``Random Number Generation'', Chapter 4 of the
Handbook on Simulation, Jerry Banks Ed., Wiley, 1998, 93--137.

@uref{http://www.iro.umontreal.ca/~lecuyer/papers.html}
in the file @file{handsim.ps}.
@end itemize

@noindent
The source code for the @sc{diehard} random number generator tests is also
available online,

@itemize @asis
@item
@cite{DIEHARD source code} G. Marsaglia,
@item
@uref{http://stat.fsu.edu/pub/diehard/}
@end itemize

@noindent
A comprehensive set of random number generator tests is available from
@sc{nist},

@itemize @asis
@item
NIST Special Publication 800-22, ``A Statistical Test Suite for the
Validation of Random Number Generators and Pseudo Random Number
Generators for Cryptographic Applications''.
@item
@uref{http://csrc.nist.gov/rng/}
@end itemize

@node Random Number Acknowledgements
@section Acknowledgements

Thanks to Makoto Matsumoto, Takuji Nishimura and Yoshiharu Kurita for
making the source code to their generators (MT19937, MM&TN; TT800,
MM&YK) available under the GNU General Public License.  Thanks to Martin
L@"uscher for providing notes and source code for the @sc{ranlxs} and
@sc{ranlxd} generators.

@comment lcg
@comment [ LCG(n) := n * 69069 mod (2^32) ]
@comment First 6: [69069, 475559465, 2801775573, 1790562961, 3104832285, 4238970681]
@comment %2^31-1   69069, 475559465, 654291926, 1790562961, 957348638, 2091487034
@comment mrg
@comment [q([x1, x2, x3, x4, x5]) := [107374182 mod 2147483647 * x1 + 104480 mod 2147483647 * x5, x1, x2, x3, x4]]
@comment
@comment cmrg
@comment [q1([x1,x2,x3]) := [63308 mod 2147483647 * x2 -183326 mod 2147483647 * x3, x1, x2],
@comment  q2([x1,x2,x3]) := [86098 mod 2145483479 * x1 -539608 mod 2145483479 * x3, x1, x2] ]
@comment  initial for q1 is [69069, 475559465, 654291926]
@comment  initial for q2 is  [1790562961, 959348806, 2093487202]

@comment tausworthe
@comment    [ b1(x) := rsh(xor(lsh(x, 13), x), 19),
@comment      q1(x) := xor(lsh(and(x, 4294967294), 12), b1(x)),
@comment      b2(x) := rsh(xor(lsh(x, 2), x), 25),
@comment      q2(x) := xor(lsh(and(x, 4294967288), 4), b2(x)),
@comment      b3(x) := rsh(xor(lsh(x, 3), x), 11),
@comment      q3(x) := xor(lsh(and(x, 4294967280), 17), b3(x)) ]
@comment      [s1, s2, s3] = [600098857, 1131373026, 1223067536] 
@comment [2948905028, 441213979, 394017882]