@cindex random number generators

The @value{GSL} provides a large collection of random number generators
which can be accessed through a uniform interface. Environment variables
allow you to select different generators and seeds at runtime, so that
you can easily switch between generators without needing to recompile
your program. Each instance of a generator keeps track of its own state,
allowing the generators to be used in multi-threaded programs.
Additional functions are available for transforming uniform random
numbers into samples from continuous or discrete probability
distributions such as the Gaussian, log-normal or Poisson distributions.

@comment Need to explain the difference between SERIAL and PARALLEL random 
@comment number generators here

@menu
* General comments on random numbers::  
* The Random Number Generator Interface::  
* Random number generator initialization::  
* Sampling from a random number generator::  
* Auxiliary random number generator functions::  
* Random number environment variables::  
* Saving and restoring random number generator state::  
* Available random number generator algorithms::  
* Random Number Generator Performance::  
* Random Number References and Further Reading::  
* Random Number Acknowledgements::  
@end menu

@node General comments on random numbers
@section General comments on random numbers

In 1988, Park and Miller wrote a paper entitled ``Random number
generators: good ones are hard to find.'' [Commun. ACM, 31, 1192--1201].
Fortunately, some excellent random number generators are available,
though poor ones are still in common use.  You may be happy with the
system-supplied random number generator on your computer, but you should
be aware that as computers get faster, requirements on random number
generators increase.  Nowadays, a simulation that calls a random number
generator millions of times can often finish before you can make it down
the hall to the coffee machine and back.

A very nice review of random number generators was written by Pierre
L'Ecuyer, as Chapter 4 of the book: Handbook on Simulation, Jerry Banks,
ed. (Wiley, 1997). The chapter is available in postscript from from
L'Ecuyer's ftp site (see references). Knuth's volume on Seminumerical
Algorithms (originally published in 1968) devotes 170 pages to random
number generators, and has recently been updated in its 3rd edition
(1997).
@comment is only now starting to show its age.
@comment Nonetheless, 
It is brilliant, a classic. If you don't own it, you should stop reading
right now, run to the nearest bookstore, and buy it.

A good random number generator will satisfy both theoretical and
statistical properties.  Theoretical properties are often hard to obtain
(they require real math!), but one prefers a random number generator
with a long period, low serial correlation, and a tendency @emph{not} to
``fall mainly on the planes.''  Statistical tests are performed with
numerical simulations.  Generally, a random number generator is used to
estimate some quantity for which the theory of probability provides an
exact answer.  Comparison to this exact answer provides a measure of
``randomness''.

@node The Random Number Generator Interface
@section The Random Number Generator Interface

It is important to remember that a random number generator is not a
``real'' function like sine or cosine.  Unlike real functions, successive
calls to a random number generator yield different return values.  Of
course that is just what you want for a random number generator, but to
achieve this effect, the generator must keep track of some kind of
``state'' variable.  Sometimes this state is just an integer (sometimes
just the value of the previously generated random number), but often it
is more complicated than that and may involve a whole array of numbers,
possibly with some indices thrown in.  To use the random number
generators, you do not need to know the details of what comprises the
state, and besides that varies from algorithm to algorithm.

The random number generator library uses two special structs,
@code{gsl_rng_type} which holds static information about each type of
generator and @code{gsl_rng} which describes an instance of a generator
created from a given @code{gsl_rng_type}.

The functions described in this section are declared in the header file
@file{gsl_rng.h}.

@node Random number generator initialization
@section Random number generator initialization

@deftypefn Random {gsl_rng *} gsl_rng_alloc (gsl_rng_type * @var{T})
This function returns a pointer to a newly-created
instance of a random number generator of type @var{T}.
For example, the following code creates an instance of the Tausworthe
generator,

@example
gsl_rng * r = gsl_rng_alloc (gsl_rng_taus);
@end example

If there is insufficient memory to create the generator then the
function returns a null pointer and the error handler is invoked with an
error code of @code{GSL_ENOMEM}.

The generator is automatically initialized with the default seed,
@code{gsl_rng_default_seed}. This is zero by default but can be changed
either directly or by using the environment variable @code{GSL_RNG_SEED},
@pxref{Random number environment variables}.

Some of the defined generator types are,

@example
gsl_rng_cmrg, gsl_rng_minstd, gsl_rng_mrg, gsl_rng_mt19937,
gsl_rng_r250, gsl_rng_ran0, gsl_rng_ran1, gsl_rng_ran2,
gsl_rng_ran3, gsl_rng_rand, gsl_rng_rand48,
gsl_rng_random_bsd, gsl_rng_random_glibc2,
gsl_rng_random_libc5, gsl_rng_randu, gsl_rng_ranf,
gsl_rng_ranlux, gsl_rng_ranlux389, gsl_rng_ranmar,
gsl_rng_slatec, gsl_rng_taus, gsl_rng_tds, gsl_rng_tt800,
gsl_rng_uni, gsl_rng_uni32, gsl_rng_vax, gsl_rng_zuf
@end example
The details of each generator are given later in this chapter.
@end deftypefn

@deftypefn Random void gsl_rng_set (const gsl_rng * @var{r}, unsigned long int @var{s})
This function initializes (or `seeds') the random number generator. If
the generator is seeded with the same value of @var{s} on two different
runs, the same stream of random numbers will be generated by successive
calls to the routines below. If different values of @var{s} are
supplied, then the generated streams of random numbers should be
completely different. If the seed @var{s} is zero then the standard seed
from the original implementation is used instead. For example, the
original Fortran source code for the @code{ranlux} generator used a seed
of 314159265, and so choosing @var{s} equal to zero reproduces this when
using @code{gsl_rng_ranlux}.
@end deftypefn

@deftypefn Random void gsl_rng_free (gsl_rng * @var{r})
This function frees all the memory associated with the generator
@var{r}.
@end deftypefn

@node  Sampling from a random number generator
@section Sampling from a random number generator

The following functions return uniformly distributed random numbers,
either as integers or double precision floating point numbers. To obtain
non-uniform distributions @pxref{Random Number Distributions}.

@deftypefn Random {unsigned long int} gsl_rng_get (const gsl_rng * @var{r})
This function returns a random integer from the generator @var{r}.  The
minimum and maximum values depend on the algorithm used, but all
integers in the range [@var{min},@var{max}] are equally likely.  The
values of @var{min} and @var{max} can determined using the auxiliary
functions @code{gsl_rng_max (r)} and @code{gsl_rng_min (r)}.
@end deftypefn

@deftypefn Random double gsl_rng_uniform (const gsl_rng * @var{r})
This function returns a double precision floating point number uniformly
distributed in the range [0,1). The range includes 0.0 but excludes 1.0.
The value is typically obtained by dividing the result of
@code{gsl_rng_get(r)} by @code{gsl_rng_max(r) + 1.0} in double
precision. Some generators compute this ratio internally so that they
can provide floating point numbers with more than 32 bits of randomness
(the maximum number of bits that can be portably represented in a single
@code{unsigned long int}).
@end deftypefn

@deftypefn Random double gsl_rng_uniform_pos (const gsl_rng * @var{r})
This function returns a positive double precision floating point number
uniformly distributed in the range (0,1), excluding both 0.0 and 1.0.
The number is obtained by sampling the generator with the algorithm of
@code{gsl_rng_uniform} until a non-zero value is obtained. You can use
this function if you need to avoid a singularity at 0.0.
@end deftypefn

@deftypefn Random {unsigned long int} gsl_rng_uniform_int (const gsl_rng * @var{r}, unsigned long int @var{n})
This function returns a random integer from 0 to @var{n-1} inclusive.
All integers in the range [0,@var{n-1}] are equally likely, regardless
of the generator used. An offset correction is applied so that zero is
always returned with the correct probability, for any minimum value of
the underlying generator.

If @var{n} is larger than the range of the generator then the function
calls the error handler with an error code of @code{GSL_EINVAL} and
returns zero.
@end deftypefn

@node Auxiliary random number generator functions
@section Auxiliary random number generator functions
The following functions provide information about an existing
generator. You should use them in preference to hard-coding the generator
parameters into your own code.

@deftypefn Random {const char *} gsl_rng_name (const gsl_rng * @var{r})
This function returns a pointer to the name of the generator.
For example,

@example
printf("r is a '%s' generator\n", gsl_rng_name (r)) ;
@end example

@noindent
would print something like @code{r is a 'taus' generator}
@end deftypefn

@deftypefn Random {unsigned long int} gsl_rng_max (const gsl_rng * @var{r})
@code{gsl_rng_max} returns the largest value that @code{gsl_rng_get}
can return.
@end deftypefn

@deftypefn Random {unsigned long int} gsl_rng_min (const gsl_rng * @var{r})
@code{gsl_rng_min} returns the smallest value that @code{gsl_rng_get}
can return. Usually this value is zero. There are some generators with
algorithms that cannot return zero, and for these generators the minimum
value is 1.
@end deftypefn

@deftypefn Random {void *} gsl_rng_state (const gsl_rng * @var{r})
@deftypefnx Random size_t gsl_rng_size (const gsl_rng * @var{r})
These function return a pointer to the state of generator @var{r} and
its size. You can use this information to access the state directly. For
example, the following code will write the state of a generator to a
stream,

@example
void * state = gsl_rng_state (r);
size_t n = gsl_rng_size (r);
fwrite (state, n, 1, stream);
@end example

@end deftypefn

@node Random number environment variables
@section Random number environment variables

The library allows you to choose a default generator and seed from the
environment variables @code{GSL_RNG_TYPE} and @code{GSL_RNG_SEED} and
the function @code{gsl_rng_env_setup}. This makes it easy try out
different generators and seeds without having to recompile your program.

@deftypefun {const gsl_rng_type *} gsl_rng_env_setup (void)
This function reads the environment variables @code{GSL_RNG_TYPE} and
@code{GSL_RNG_SEED} and uses their values to set the corresponding
library variables @code{gsl_rng_default} and
@code{gsl_rng_default_seed}. These global variables are defined as
follows,

@example
extern const gsl_rng_type *gsl_rng_default
extern unsigned long int gsl_rng_default_seed
@end example

The environment variable @code{GSL_RNG_TYPE} should be the name of a
generator, such as @code{taus} or @code{mt19937}. The environment
variable @code{GSL_RNG_SEED} should contain the desired seed value. It
is converted to an @code{unsigned long int} using the C library function
@code{strtoul}.

If you don't specify a generator for @code{GSL_RNG_TYPE} then
@code{gsl_rng_mt19937} is used as the default. The initial value of
@code{gsl_rng_default_seed} is zero.

@end deftypefun
@noindent
Here is a short program which shows how to create a global
generator using the environment variables @code{GSL_RNG_TYPE} and
@code{GSL_RNG_SEED},

@example
#include <stdio.h>
#include <gsl_rng.h>

gsl_rng * r ;  /* global generator */

int 
main ()
@{
  gsl_rng_env_setup() ;

  r = gsl_rng_alloc (gsl_rng_default);
  
  printf("generator type: %s\n", gsl_rng_name (r));
  printf("seed = %u\n", gsl_rng_default_seed);
  printf("first value = %u\n", gsl_rng_get (r)) ;
@}
@end example

@noindent
Running the program without any environment variables uses the initial
defaults, an @code{mt19937} generator with a seed of 0,

@example
bash$ ./a.out 
generator type: mt19937
seed = 0
first value = 3510405877
@end example

@noindent
By setting the two variables on the command line we can
change the default generator and the seed,

@example
bash$ GSL_RNG_TYPE="taus" GSL_RNG_SEED=123 ./a.out 
GSL_RNG_TYPE=taus
GSL_RNG_SEED=123
generator type: taus
seed = 123
first value = 2720986350
@end example

@node Saving and restoring random number generator state
@section Saving and restoring random number generator state

The above methods ignore the random number `state' which changes from
call to call.  It is often useful to be able to save and restore the
state.  To permit these practices, a few somewhat more advanced
functions are supplied.  These include:

@deftypefn Random {gsl_rng *} gsl_rng_cpy (gsl_rng * @var{dest}, const gsl_rng * @var{src})
This function copies the random number generator @var{src} into the
pre-existing generator @var{dest}, making @var{dest} into an exact copy
of @var{src}. It returns @var{dest} if successful and a null pointer if
sufficient memory could not be allocated.
@end deftypefn

@deftypefn Random {gsl_rng *} gsl_rng_clone (const gsl_rng * @var{r})
This function returns a pointer to a newly created generator which is an
exact copy of the generator @var{r}.
@end deftypefn

@deftypefn Random void gsl_rng_print_state (const gsl_rng * @var{r})
This function prints a hex-dump of the state of the generator @var{r} to
@code{stdout}. At the moment its only use is for debugging.
@end deftypefn

@node Available random number generator algorithms
@section Available random number generator algorithms

The functions described above make no reference to the actual algorithm
used. This is deliberate so that you can switch algorithms without
having to change any of your application source code. The library
provides a large number of generators of different types, including
simulation quality generators, generators provided for compatibility
with other libraries and historical generators from the past.

@menu
* Simulation quality generators::  
* Unix random number generators::  
* Numerical Recipes generators::  
* Other random number generators::  
@end menu

@node Simulation quality generators
@subsection Simulation quality generators

The following generators are recommended for use in simulation. They
have extremely long periods, low correlation and pass most statistical
tests.

@deffn {Generator} gsl_rng_mt19937
@cindex MT19937 random number generator
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 
@comment
@c{$2^{19937} - 1$} 
@math{2^19937 - 1} (about 
@c{$10^{6000}$}
@math{10^6000}) and is
equi-distributed in 623 dimensions. It has passed the @sc{diehard}
statistical tests. It uses 624 words of state per generator and is
comparable in speed to the other generators. The original generator used
a default seed of 4357 and choosing @var{s} equal to zero in
@code{gsl_rng_set} reproduces this.

For more information see,
@itemize @asis
@item
Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A
623-dimensionally equidistributed uniform pseudorandom number
generator". @cite{ACM Transactions on Modeling and Computer
Simulation}, Vol. 8, No. 1 (Jan. 1998), Pages 3-30
@end itemize
@end deffn

@deffn {Generator} gsl_rng_ranlxs0
@deffnx {Generator} gsl_rng_ranlxs1
@deffnx {Generator} gsl_rng_ranlxs2
@cindex RANLXS random number generator

The generator @code{ranlxs0} is a second-generation version of the
@sc{ranlux} algorithm of L@"uscher, which produces "luxury random
numbers".  This generator provides single precision output (24 bits) at
three luxury levels @code{ranlxs0}, @code{ranlxs1} and @code{ranlxs2}.
It uses double-precision floating point arithmetic internally and can be
significantly faster than the integer version of @code{ranlux},
particularly on 64-bit architectures.  The period of the generator is
about @c{$10^{171}$} 
@math{10^171}.  The algorithm has mathematically proven properties and
can provide truly decorrelated numbers at a known level of randomness.
@end deffn

@deffn {Generator} gsl_rng_ranlxd1
@deffnx {Generator} gsl_rng_ranlxd2
@cindex RANLXD random number generator

These generators produce double precision output (48 bits) from the
@sc{ranlxs} generator. The library provides two luxury levels
@code{ranlxd1} and @code{ranlxd2}.
@end deffn


@deffn {Generator} gsl_rng_ranlux
@deffnx {Generator} gsl_rng_ranlux389

@cindex RANLUX random number generator
The @code{ranlux} generator is an implemenation of the original
algorithm developed by L@"uscher. 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
@sc{ranlxs} and @sc{ranlxd} described above provide floating-point
implementations which will be faster on many platforms.
The period of the generator is about @c{$10^{171}$} 
@math{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@"uscher
is provided by @code{gsl_rng_ranlux}, while @code{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,
@itemize @asis
@item
M. L@"uscher, "A portable high-quality random number generator for
lattice field theory calculations", @cite{Computer Physics
Communications}, 79 (1994) 100-110.
@item
F. James, "RANLUX: A Fortran implementation of the high-quality
pseudo-random number generator of L@"uscher", @cite{Computer Physics
Communications}, 79 (1994) 111-114
@end itemize
@end deffn


@deffn {Generator} gsl_rng_cmrg
@cindex CMRG, combined multiple recursive random number generator
This is a combined multiple recursive generator by L'Ecuyer. 
Its sequence is,

@tex
\beforedisplay
$$
z_n = (x_n - y_n) \,\hbox{mod}\, m_1
$$
\afterdisplay
@end tex
@ifinfo
@example
z_n = (x_n - y_n) mod m_1
@end example
@end ifinfo
@noindent
where the two underlying generators 
@c{$x_n$}
@math{x_n} and 
@c{$y_n$}
@math{y_n} are,

@tex
\beforedisplay
$$
\eqalign{ 
x_n & = (a_1 x_{n-1} + a_2 x_{n-2} + a_3 x_{n-3}) \,\hbox{mod}\, m_1 \cr
y_n & = (b_1 y_{n-1} + b_2 y_{n-2} + b_3 y_{n-3}) \,\hbox{mod}\, m_2
}
$$
\afterdisplay
@end tex
@ifinfo
@example
x_n = (a_1 x_@{n-1@} + a_2 x_@{n-2@} + a_3 x_@{n-3@}) mod m_1
y_n = (b_1 y_@{n-1@} + b_2 y_@{n-2@} + b_3 y_@{n-3@}) mod m_2
@end example
@end ifinfo

@noindent
with coefficients 
@math{a_1 = 0}, 
@math{a_2 = 63308}, 
@math{a_3 = -183326},
@math{b_1 = 86098}, 
@math{b_2 = 0},
@math{b_3 = -539608},
and moduli 
@c{$m_1 = 2^{31} - 1 = 2147483647$} 
@math{m_1 = 2^31 - 1 = 2147483647}
and 
@c{$m_2 = 2145483479$}
@math{m_2 = 2145483479}.

The period of this generator is 
@c{$2^{205}$}
@math{2^205} 
(about 
@c{$10^{61}$}
@math{10^61}). It uses
6 words of state per generator. For more information see,

@itemize @asis
@item
P. L'Ecuyer, "Combined Multiple Recursive Random Number
Generators," @cite{Operations Research}, 44, 5 (1996), 816--822.
@end itemize
@end deffn

@deffn {Generator} gsl_rng_mrg
@cindex MRG, multiple recursive random number generator
This is a fifth-order multiple recursive generator by L'Ecuyer, Blouin
and Coutre.  Its sequence is,

@tex
\beforedisplay
$$
x_n = (a_1 x_{n-1} + a_5 x_{n-5}) \,\hbox{mod}\, m
$$
\afterdisplay
@end tex
@ifinfo
@example
x_n = (a_1 x_@{n-1@} + a_5 x_@{n-5@}) mod m
@end example
@end ifinfo

@noindent
with 
@c{$a_1 = 107374182$} 
@math{a_1 = 107374182}, 
@c{$a_2 = a_3 = a_4 = 0$}
@math{a_2 = a_3 = a_4 = 0}, 
@c{$a_5 = 104480$}
@math{a_5 = 104480}
and 
@c{$m = 2^{31}-1$}
@math{m = 2^31 - 1}.

The period of this generator is about 
@c{$10^{46}$}
@math{10^46}. It uses 5 words
of state per generator. More information can be found in the following
paper,
@itemize @asis
@item
P. L'Ecuyer, F. Blouin, and R. Coutre, "A search for good multiple
recursive random number generators", @cite{ACM Transactions on Modeling and
Computer Simulation} 3, 87-98 (1993).
@end itemize
@end deffn

@deffn {Generator} gsl_rng_taus
@cindex Tausworthe random number generator
This is a maximally equidistributed combined Tausworthe generator by
L'Ecuyer. The sequence is,

@tex
\beforedisplay
$$
x_n = (s^1_n \oplus s^2_n \oplus s^3_n) 
$$
\afterdisplay
@end tex
@ifinfo
@example
x_n = (s1_n ^^ s2_n ^^ s3_n) 
@end example
@end ifinfo

@noindent
where,

@tex
\beforedisplay
$$
\eqalign{
s^1_{n+1} &= (((s^1_n \& 4294967294) <<12) \oplus (((s^1_n <<13) \oplus s^1_n) >>19)) \cr
s^2_{n+1} &= (((s^2_n \& 4294967288) << 4) \oplus (((s^2_n << 2) \oplus s^2_n) >>25)) \cr
s^3_{n+1} &= (((s^3_n \& 4294967280) <<17) \oplus (((s^3_n << 3) \oplus s^3_n) >>11))
}
$$
\afterdisplay
@end tex
@ifinfo
@example
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))
@end example
@end ifinfo

@noindent
computed modulo 
@c{$2^{32}$}
@math{2^32}. In the formulas above 
@c{$\oplus$}
@math{^^}
denotes ``exclusive-or''. Note that the algorithm relies on the properties
of 32-bit unsigned integers and has been implemented using a bitmask
of @code{0xFFFFFFFF} to make it work on 64 bit machines.

The period of this generator is @c{$2^{88}$}
@math{2^88} (about
@c{$10^{26}$}
@math{10^26}). It uses 3 words of state per generator. For more
information see,

@itemize @asis
@item
P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
Generators", @cite{Mathematics of Computation}, 65, 213 (1996), 203--213.
@end itemize
@end deffn

@deffn {Generator} gsl_rng_gfsr4
@cindex Four-tap Generalized Feedback Shift Register
The @code{gfsr4} generator is like a lagged-fibonacci generator, and 
produces each number as an @code{xor}'d sum of four previous values.

@tex
\beforedisplay
$$
r_n = r_{n-A} \oplus r_{n-B} \oplus r_{n-C} \oplus r_{n-D}
$$
\afterdisplay
@end tex
@ifinfo
@example
r_n = r_@{n-A@} ^^ r_@{n-B@} ^^ r_@{n-C@} ^^ r_@{n-D@}
@end example
@end ifinfo

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 defn 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 the example on p392 of
Ziff's article: @math{A=471}, @math{B=1586}, @math{C=6988}, @math{D=9689}.

If the offsets are appropriately chosen (such the one ones in
this implementation), then the sequence is said to be maximal.
I'm not sure what that means, but I would guess that means all
states are part of the same cycle, which would mean that the
period for this generator is astronomical; it is
@c{$(2^K)^D \approx 10^{93334}$}
@math{(2^K)^D \approx 10^@{93334@}}
where @math{K=32} is the number of bits in the word, and D is the longest
lag.  This would also mean that any one random number could 
easily be zero; ie 
@c{$0 \le r < 2^{32}$}
@math{0 <= r < 2^32}.

Ziff doesn't say so, but it seems to me that the bits are
completely independent here, so one could use this as an efficient
bit generator; each number supplying 32 random bits.

For more information see,
@itemize @asis
@item
Robert M. Ziff, "Four-tap shift-register-sequence random-number 
generators", @cite{Computers in Physics}, 12(4), Jul/Aug
1998, pp 385-392.
@end itemize
@end deffn

@node Unix random number generators
@subsection Unix random number generators

The standard Unix random number generators @code{rand}, @code{random}
and @code{rand48} are provided as part of GSL. Although these
generators are widely available individually often they aren't all
available on the same platform. This makes it difficult to write
portable code using them and so we have included the complete set of
Unix generators in GSL for convenience. Note that these generators
don't produce high-quality randomness and aren't suitable for work
requiring accurate statistics. However, if you won't be measuring
statistical quantities and just want to introduce some variation into
your program then these generators are quite acceptable.

@cindex BSD random number generator, rand
@cindex Unix random number generators, rand
@cindex Unix random number generators, rand48

@deffn {Generator} gsl_rng_rand
@cindex BSD random number generator
This is the BSD @code{rand()} generator. 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 
@c{$a = 1103515245$}
@math{a = 1103515245}, 
@c{$c = 12345$}
@math{c = 12345} and 
@c{$m = 2^{31}$}
@math{m = 2^31}.
The seed specifies the initial value, 
@c{$x_1$}
@math{x_1}. The period of this
generator is 
@c{$2^{31}$}
@math{2^31}, and it uses 1 word of storage per
generator.
@end deffn

@deffn {Generator} gsl_rng_random_bsd
@deffnx {Generator} gsl_rng_random_libc5
@deffnx {Generator} gsl_rng_random_glibc2
These generators implement the @code{random()} family of functions, a
set of linear feedback shift register generators originally used in BSD
Unix. There are several versions of @code{random()} in use today: the
original BSD version (e.g. on SunOS4), a libc5 version (common on
existing 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 @code{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,

@example
gsl_rng_random8_bsd
gsl_rng_random32_bsd
gsl_rng_random64_bsd
gsl_rng_random128_bsd
gsl_rng_random256_bsd
@end example

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

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

@node Numerical Recipes generators
@subsection Numerical Recipes generators
@cindex Random number generators, Numerical recipes
@cindex Numerical recipes, random number generators
@comment
The following generators are provided for compatibility with
@cite{Numerical Recipes}. Note that the original Numerical Recipes
functions used single precision while we use double precision. This will
lead to minor discrepancies, but only at the level of single-precision
rounding error. If necessary you can force the returned values to single
precision by storing them in a @code{volatile float}, which prevents the
value being held in a register with double or extended precision. Apart
from this difference the underlying algorithms for the integer part of
the generators are the same.

@deffn {Generator} gsl_rng_ran0 
Numerical recipes @code{ran0} implements Park and Miller's @sc{minstd}
algorithm with a modified seeding procedure.
@end deffn

@deffn {Generator} gsl_rng_ran1 
Numerical recipes @code{ran1} implements Park and Miller's @sc{minstd}
algorithm with a 32-element Bayes-Durham shuffle box.
@end deffn

@deffn {Generator} gsl_rng_ran2 
Numerical recipes @code{ran2} implements a L'Ecuyer combined recursive
generator with a 32-element Bayes-Durham shuffle-box.
@end deffn

@deffn {Generator} gsl_rng_ran3 
Numerical recipes @code{ran3} implements Knuth's portable
subtractive generator.
@end deffn

@node Other random number generators
@subsection 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.

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

@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, 
@c{$x_1$}
@math{x_1}, with the lowest bit set to
prevent the seed taking an even value.  The upper 16 bits of 
@c{$x_1$}
@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.

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 
@c{$x_n/m$}
@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
From: 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, 
@c{$x_1$}
@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, 
@c{$x_1$}
@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 generalisation 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.

@smallexample
  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 smallexample

@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, available at
@url{http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handsim.ps}.

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.

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

@itemize @asis
@item
@cite{DIEHARD source code} 
G. Marsaglia
@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]