diff options
Diffstat (limited to 'gsl-1.9/doc/rng.texi')
| -rw-r--r-- | gsl-1.9/doc/rng.texi | 1456 |
1 files changed, 1456 insertions, 0 deletions
diff --git a/gsl-1.9/doc/rng.texi b/gsl-1.9/doc/rng.texi new file mode 100644 index 0000000..a947f31 --- /dev/null +++ b/gsl-1.9/doc/rng.texi @@ -0,0 +1,1456 @@ +@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] |