rng.texi

开放gsl矩阵运算

@end deffn

@node Other random number generators
@section 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, 
@c{$2^{31}$}
@math{2^31} or 
@c{$2^{32}$}
@math{2^32}).  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.

@deffn {Generator} gsl_rng_ranf
@cindex RANF random number generator
@cindex CRAY random number generator, RANF
This is the CRAY random number generator @code{RANF}.  Its 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
defined on 48-bit unsigned integers with @math{a = 44485709377909} and
@c{$m = 2^{48}$}
@math{m = 2^48}.  The seed specifies the lower
32 bits of the initial value, 
@math{x_1}, with the lowest bit set to
prevent the seed taking an even value.  The upper 16 bits of 
@math{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 compatibile 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 @math{a} mod @math{m}.  This is done for compatibility with
the original CRAY implementation.

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

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

The period of this generator is @c{$2^{46}$}
@math{2^46}.
@end deffn

@deffn {Generator} gsl_rng_ranmar
@cindex RANMAR random number generator
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.
@end deffn

@deffn {Generator} gsl_rng_r250
@cindex shift-register random number generator
@cindex R250 shift-register random number generator
This is the shift-register generator of Kirkpatrick and Stoll.  The
sequence is

@tex
\beforedisplay
$$ 
x_n = x_{n-103} \oplus x_{n-250}
$$
\afterdisplay
@end tex
@ifinfo
@example
x_n = x_@{n-103@} ^^ x_@{n-250@}
@end example
@end ifinfo
@noindent
where 
@c{$\oplus$}
@math{^^} denote ``exclusive-or'', defined on
32-bit words.  The period of this generator is about @c{$2^{250}$}
@math{2^250} and it
uses 250 words of state per generator.

For more information see,
@itemize @asis
@item
S. Kirkpatrick and E. Stoll, "A very fast shift-register sequence random
number generator", @cite{Journal of Computational Physics}, 40, 517-526
(1981)
@end itemize
@end deffn

@deffn {Generator} gsl_rng_tt800
@cindex TT800 random number generator
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 
@c{$2^{800}$}
@math{2^800} and uses 33 words of storage
per generator.

For more information see,
@itemize @asis
@item
Makoto Matsumoto and Yoshiharu Kurita, "Twisted GFSR Generators
II", @cite{ACM Transactions on Modelling and Computer Simulation},
Vol. 4, No. 3, 1994, pages 254-266.
@end itemize
@end deffn

@comment The following generators are included only for historical reasons, so
@comment that you can reproduce results from old programs which might have used
@comment them.  These generators should not be used for real simulations since
@comment they have poor statistical properties by modern standards.

@deffn {Generator} gsl_rng_vax
@cindex VAX random number generator
This is the VAX generator @code{MTH$RANDOM}.  Its sequence is,

@tex
\beforedisplay
$$
x_{n+1} = (a x_n + c) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo
@example
x_@{n+1@} = (a x_n + c) mod m
@end example
@end ifinfo
@noindent
with 
@math{a = 69069}, @math{c = 1} and 
@c{$m = 2^{32}$}
@math{m = 2^32}.  The seed specifies the initial value, 
@math{x_1}.  The
period of this generator is 
@c{$2^{32}$}
@math{2^32} and it uses 1 word of storage per
generator.
@end deffn

@deffn {Generator} gsl_rng_transputer
This is the random number generator from the INMOS Transputer
Development system.  Its 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
with @math{a = 1664525} and 
@c{$m = 2^{32}$}
@math{m = 2^32}.
The seed specifies the initial value, 
@c{$x_1$}
@math{x_1}.
@end deffn

@deffn {Generator} gsl_rng_randu
@cindex RANDU random number generator
This is the IBM @code{RANDU} generator.  Its 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
with @math{a = 65539} and 
@c{$m = 2^{31}$}
@math{m = 2^31}.  The
seed specifies the initial value, 
@math{x_1}.  The period of this
generator was only 
@c{$2^{29}$}
@math{2^29}.  It has become a textbook example of a
poor generator.
@end deffn

@deffn {Generator} gsl_rng_minstd
@cindex RANMAR random number generator
This is Park and Miller's "minimal standard" @sc{minstd} generator, a
simple linear congruence which takes care to avoid the major pitfalls of
such algorithms.  Its 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
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

@node Random Number Generator Performance
@section Random Number Generator 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 simulation quality generators
which offer the best performance are @code{taus}, @code{gfsr4} and
@code{mt19937}.

@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 References and Further Reading
@section References and Further Reading
@noindent
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.

@url{http://www.iro.umontreal.ca/~lecuyer/papers.html}
in the file @file{handsim.ps}.
@end itemize
@noindent
On the World Wide Web, see the pLab home page
(@url{http://random.mat.sbg.ac.at/}) for a lot of information on the
state-of-the-art in random number generation, and for numerous links to
various "random" WWW sites.

@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
@url{http://stat.fsu.edu/pub/diehard/}
@end itemize

@node Random Number Acknowledgements
@section Acknowledgements
@noindent
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]