http://www.uni-karlsruhe.de/~RNG/

Random number generators

-------------------------------------------------------------------- Diese Seite gibt es noch nicht in Deutsch. --------------------------------------------------------------------

Classification of random numbers

Random numbers for use in computer programs can be classified into 3 different categories:

* Truely random numbers: Truely random numbers obviosly cannot be produced by computer programs, they must be supplied by an external source like radioactive decay. Such sequences are available (e.g. on magnetic tape), but clumsy to use and often not sufficient in terms of speed and number. * Pseudorandom numbers: A sequence of numbers is generated by an algorithm in a way that the resulting numbers look statistically independent and uniformly distributed. This is the prevailing method used in random number generators. * Quasirandom numbers: These are generated by algorithms tuned to optimize the sequences uniform distribution, which can improve the accuracy of Monte-Carlo integration. These numbers are not independent and thus cannot be used generally.

Other than uniform distributions can be generated by suitable transformations of the basic uniformly distributed sequence. Numerical libraries often offer a rich set of distributions.

Desirable properties of (pseudo) random numbers

A good random number generator (RNG) should have the following properties:

* Good statistical properties: There are theoretical and empirical tests to judge a RNGs quality. Every generator should always be tested with one's actual application: the standard tests can only disqualify a RNG and may not check for the properties the application requires. * Long period: RNG algorithms are iteration formulae. The state is often stored in a single integer, in this case there cannot be more states than representable integers (recall 2^30 \approx 10^9). * Reproducibility: All generators can initialize the sequence by a starting seed. Storing and reloading a generator's internal state is also useful. * Portability: This concerns both programming language (e.g. Fortran 90 or ANSI C) as well as machine-dependent (e.g. floating point representation) aspects. The ideal RNG produces (bit-) identical results in every environment. * Efficient implementation: This may be irrelevant for "general purpose" generators. But time-critical applications may require inline coding and/or the generation of whole vectors of random numbers at once. Vector and parallel computers need special RNG methods.

Which of these aspects is most important depends on the actual application, of course.

Miscellaneous RNG material

What follows is a collection of material on pseudorandom number generators. I hope to improve this soon...

* The RNG Chapter of Designing and Building Parallel Programs by Ian Foster * The pLab pages at Salzburg University * The RNG Document of ORNL's Computational Science Education Project * My publications on RNGs are available online, also some slides * My BiBTeX-bibliographies of articles and books on random number generation * The RAND/VP package contains a RNG tuned for our vector computer SNI S600/20 * The NAG and IMSL Fortran libraries contain random number generators for various distributions * Popular public-domain sources include the StatLib and NetLib libraries * My publications on RNGs and the RANEXP library are available by anonymous ftp also. URL: ftp://ftp.rz.uni-karlsruhe.de/pub/misc/random/ * A good source of RNG codes and articles is the journal Computer Physics Communications, ISSN 0010-4655, published by North-Holland.

-------------------------------------------------------------------- Michael Hennecke / 21.07.1995