[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Random number generators

>    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