From: anonymous-remailer@shell.portal.com
Date: Wed, 4 Oct 95 11:23:15 PDT
To: cypherpunks@toad.com
Subject: Random number generators
Message-ID: <199510041822.LAA22783@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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