Module rgsl::types::rng [−][src]
Expand description
Random Number Generation
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.
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). 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 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”.
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, RngType which holds static information about each type of generator and Rng which describes an instance of a generator created from a given RngType.
Performance
The following table shows the relative performance of a selection the available random number generators. The fastest simulation quality generators are taus, gfsr4 and mt19937. The generators which offer the best mathematically-proven quality are those based on the RANLUX algorithm.
- 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
Random number environment variables
The library allows you to choose a default generator and seed from the environment variables GSL_RNG_TYPE and GSL_RNG_SEED and the function gsl_rng_env_setup. This makes it easy try out different generators and seeds without having to recompile your program.
References and Further Reading
The subject of random number generation and testing is reviewed extensively in Knuth’s Seminumerical Algorithms.
Donald E. Knuth, The Art of Computer Programming: Seminumerical Algorithms (Vol 2, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896842. Further information is available in the review paper written by Pierre L’Ecuyer,
P. L’Ecuyer, “Random Number Generation”, Chapter 4 of the Handbook on Simulation, Jerry Banks Ed., Wiley, 1998, 93–137. http://www.iro.umontreal.ca/~lecuyer/papers.html
The source code for the DIEHARD random number generator tests is also available online,
DIEHARD source code G. Marsaglia, http://stat.fsu.edu/pub/diehard/ A comprehensive set of random number generator tests is available from NIST,
NIST Special Publication 800-22, “A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications”. http://csrc.nist.gov/rng/
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üscher for providing notes and source code for the RANLXS and RANLXD generators.
Modules
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.
Other random number generators
The standard Unix random number generators rand, random and 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.