| @cindex random number generators |
| |
| The library 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. |
| |
| These functions are declared in the header file @file{gsl_rng.h}. |
| |
| @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:: |
| * Copying random number generator state:: |
| * Reading and writing random number generator state:: |
| * Random number generator algorithms:: |
| * Unix random number generators:: |
| * Other random number generators:: |
| * Random Number Generator Performance:: |
| * Random Number Generator Examples:: |
| * 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 |
| 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 |
| |
| @deftypefun {gsl_rng *} gsl_rng_alloc (const 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}). |
| |
| The details of the available generator types are |
| described later in this chapter. |
| @end deftypefun |
| |
| @deftypefun 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 deftypefun |
| |
| @deftypefun void gsl_rng_free (gsl_rng * @var{r}) |
| This function frees all the memory associated with the generator |
| @var{r}. |
| @end deftypefun |
| |
| @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}. |
| |
| @deftypefun {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 deftypefun |
| |
| @deftypefun 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 deftypefun |
| |
| @deftypefun 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 deftypefun |
| |
| @deftypefun {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 @math{n-1} inclusive |
| by scaling down and/or discarding samples from the generator @var{r}. |
| All integers in the range @math{[0,n-1]} are produced with equal |
| probability. For generators with a non-zero minimum value an offset |
| is applied so that zero is returned with the correct probability. |
| |
| Note that this function is designed for sampling from ranges smaller |
| than the range of the underlying generator. The parameter @var{n} |
| must be less than or equal to the range of the generator @var{r}. |
| 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. |
| |
| In particular, this function is not intended for generating the full range of |
| unsigned integer values @c{$[0,2^{32}-1]$} |
| @math{[0,2^32-1]}. Instead |
| choose a generator with the maximal integer range and zero mimimum |
| value, such as @code{gsl_rng_ranlxd1}, @code{gsl_rng_mt19937} or |
| @code{gsl_rng_taus}, and sample it directly using |
| @code{gsl_rng_get}. The range of each generator can be found using |
| the auxiliary functions described in the next section. |
| @end deftypefun |
| |
| @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. |
| |
| @deftypefun {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 deftypefun |
| |
| @deftypefun {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 deftypefun |
| |
| @deftypefun {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 deftypefun |
| |
| @deftypefun {void *} gsl_rng_state (const gsl_rng * @var{r}) |
| @deftypefunx size_t gsl_rng_size (const gsl_rng * @var{r}) |
| These functions 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 deftypefun |
| |
| @deftypefun {const gsl_rng_type **} gsl_rng_types_setup (void) |
| This function returns a pointer to an array of all the available |
| generator types, terminated by a null pointer. The function should be |
| called once at the start of the program, if needed. The following code |
| fragment shows how to iterate over the array of generator types to print |
| the names of the available algorithms, |
| |
| @example |
| const gsl_rng_type **t, **t0; |
| |
| t0 = gsl_rng_types_setup (); |
| |
| printf ("Available generators:\n"); |
| |
| for (t = t0; *t != 0; t++) |
| @{ |
| printf ("%s\n", (*t)->name); |
| @} |
| @end example |
| @end deftypefun |
| |
| @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 |
| @need 2000 |
| 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 |
| @verbatiminclude examples/rng.c |
| @end example |
| |
| @noindent |
| Running the program without any environment variables uses the initial |
| defaults, an @code{mt19937} generator with a seed of 0, |
| |
| @example |
| $ ./a.out |
| @verbatiminclude examples/rng.out |
| @end example |
| |
| @noindent |
| By setting the two variables on the command line we can |
| change the default generator and the seed, |
| |
| @example |
| $ 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 Copying random number generator state |
| @section Copying random number generator state |
| |
| The above methods do not expose 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: |
| |
| @deftypefun int gsl_rng_memcpy (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}. The two generators must be of the same type. |
| @end deftypefun |
| |
| @deftypefun {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 deftypefun |
| |
| @node Reading and writing random number generator state |
| @section Reading and writing random number generator state |
| |
| The library provides functions for reading and writing the random |
| number state to a file as binary data or formatted text. |
| |
| @deftypefun int gsl_rng_fwrite (FILE * @var{stream}, const gsl_rng * @var{r}) |
| This function writes the random number state of the random number |
| generator @var{r} to the stream @var{stream} in binary format. The |
| return value is 0 for success and @code{GSL_EFAILED} if there was a |
| problem writing to the file. Since the data is written in the native |
| binary format it may not be portable between different architectures. |
| @end deftypefun |
| |
| @deftypefun int gsl_rng_fread (FILE * @var{stream}, gsl_rng * @var{r}) |
| This function reads the random number state into the random number |
| generator @var{r} from the open stream @var{stream} in binary format. |
| The random number generator @var{r} must be preinitialized with the |
| correct random number generator type since type information is not |
| saved. The return value is 0 for success and @code{GSL_EFAILED} if |
| there was a problem reading from the file. The data is assumed to |
| have been written in the native binary format on the same |
| architecture. |
| @end deftypefun |
| |
| @node Random number generator algorithms |
| @section 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. |
| |
| The following generators are recommended for use in simulation. They |
| have extremely long periods, low correlation and pass most statistical |
| tests. For the most reliable source of uncorrelated numbers, the |
| second-generation @sc{ranlux} generators have the strongest proof of |
| randomness. |
| |
| @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. Later versions switched to 5489 |
| as the default seed, you can choose this explicitly via @code{gsl_rng_set} |
| instead if you require it. |
| |
| 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 |
| |
| @noindent |
| The generator @code{gsl_rng_mt19937} uses the second revision of the |
| seeding procedure published by the two authors above in 2002. The |
| original seeding procedures could cause spurious artifacts for some seed |
| values. They are still available through the alternative generators |
| @code{gsl_rng_mt19937_1999} and @code{gsl_rng_mt19937_1998}. |
| @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}, |
| in increasing order of strength. |
| 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. |
| The higher luxury levels provide increased decorrelation between samples |
| as an additional safety margin. |
| @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}, in increasing order of strength. |
| @end deffn |
| |
| |
| @deffn {Generator} gsl_rng_ranlux |
| @deffnx {Generator} gsl_rng_ranlux389 |
| |
| @cindex RANLUX random number generator |
| The @code{ranlux} generator is an implementation 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 @math{x_n} and @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{$\hbox{lcm}(m_1^3-1, m_2^3-1)$} |
| @math{lcm(m_1^3-1, m_2^3-1)}, |
| which is approximately |
| @c{$2^{185}$} |
| @math{2^185} |
| (about |
| @c{$10^{56}$} |
| @math{10^56}). 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 |
| @math{a_1 = 107374182}, |
| @math{a_2 = a_3 = a_4 = 0}, |
| @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 |
| @deffnx {Generator} gsl_rng_taus2 |
| @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)\ll 12) \oplus (((s^1_n\ll 13) \oplus s^1_n)\gg 19)) \cr |
| s^2_{n+1} &= (((s^2_n \& 4294967288)\ll 4) \oplus (((s^2_n\ll 2) \oplus s^2_n)\gg 25)) \cr |
| s^3_{n+1} &= (((s^3_n \& 4294967280)\ll 17) \oplus (((s^3_n\ll 3) \oplus s^3_n)\gg 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 |
| |
| @noindent |
| The generator @code{gsl_rng_taus2} uses the same algorithm as |
| @code{gsl_rng_taus} but with an improved seeding procedure described in |
| the paper, |
| |
| @itemize @asis |
| @item |
| P. L'Ecuyer, ``Tables of Maximally Equidistributed Combined LFSR |
| Generators'', @cite{Mathematics of Computation}, 68, 225 (1999), 261--269 |
| @end itemize |
| |
| @noindent |
| The generator @code{gsl_rng_taus2} should now be used in preference to |
| @code{gsl_rng_taus}. |
| @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 definition 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 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 as the one ones in this |
| implementation), then the sequence is said to be maximal; that means |
| that the period is @math{2^D - 1}, where @math{D} is the longest lag. |
| (It is one less than @math{2^D} because it is not permitted to have all |
| zeros in the @code{ra[]} array.) For this implementation with |
| @math{D=9689} that works out to about @c{$10^{2917}$} |
| @math{10^2917}. |
| |
| Note that the implementation of this generator using a 32-bit |
| integer amounts to 32 parallel implementations of one-bit |
| generators. One consequence of this is that the period of this |
| 32-bit generator is the same as for the one-bit generator. |
| Moreover, this independence means that all 32-bit patterns are |
| equally likely, and in particular that 0 is an allowed random |
| value. (We are grateful to Heiko Bauke for clarifying for us these |
| properties of GFSR random number generators.) |
| |
| 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 |
| @section 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 rand, BSD random number generator |
| @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 |
| @math{a = 1103515245}, |
| @math{c = 12345} and |
| @c{$m = 2^{31}$} |
| @math{m = 2^31}. |
| The seed specifies the initial value, |
| @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 (found on |
| older 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 |
| @math{a = 25214903917}, |
| @math{c = 11} and |
| @c{$m = 2^{48}$} |
| @math{m = 2^48}. |
| The seed specifies the upper 32 bits of the initial value, @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 @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 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 compatible 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 based on the recurrence |
| @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{^^} denotes ``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 |
| |
| @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] |