next up previous contents index CD CD Algorithms
Next: Factoring and Primality Testing Up: Numerical Problems Previous: Linear Programming

Random Number Generation



Input description: Nothing, or perhaps a seed.

Problem description: Generate a sequence of random integers.

Discussion: Random number generation forms the foundation behind such standard algorithmic techniques as simulated annealing and Monte Carlo integration. Discrete event simulations, used to model everything from transportation systems to casino poker, all run on streams of random numbers. Initial passwords and cryptographic keys are typically generated randomly. New developments in randomized algorithms for graph and geometric problems are revolutionizing these fields and establishing randomization as one of the fundamental ideas of computer science.           

Unfortunately, generating random numbers is a task that looks a lot easier than it really is, primarily because it is fundamentally impossible to produce truly random numbers on any deterministic device.   Von Neumann [vN63] said it best: ``Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.''   All we can hope for are pseudorandom numbers, a stream of numbers that appear as if they were generated randomly.

There can be serious consequences to using a bad random number generator. For example, the security of an Internet password scheme was recently invalidated with the discovery that its keys were produced using a random number generator of such small period that brute-force search quickly exhausted all possible passwords. The accuracy of simulations is regularly compromised or invalidated by poor random number generation.   Bottom line: This is an area where people shouldn't mess around, but they do. Issues to think about include:    

Implementations: An excellent WWW page on random number generation and stochastic simulation is available at It includes pointers to papers and literally dozens of implementations of random number generators. From there are accessible pLab [Lee94] and DIEHARD, systems for testing the quality of random number generators.    

The Stanford Graphbase (see Section gif) contains a machine-independent random number generator based on the recurrence tex2html_wrap_inline27383 . With the proper initialization, this generator has a period of at least tex2html_wrap_inline27385 .    

Algorithm 488 [Bre74], Algorithm 599 [AKD83], and Algorithm 712 [Lev92] of the Collected Algorithms of the ACM are Fortran codes for generating random numbers according to several probability distributions, including normal, exponential, and Poisson distributions. They are available from Netlib (see Section gif).         

Sim++ is a library of routines for implementing discrete event simulations, built by Robert Cubert and Paul Fishwick, of the University of Florida. It contains random number generators for a variety of different distributions, including uniform, exponential, and normal. Check out tex2html_wrap_inline27387 fishwick/simpack/simpack.html if you need a random number generator to control a simulation. Fishwick's book [Fis95] describes model design using SimPack.     

LEDA (see Section gif) provides a comprehensive random source in C++ for generating random bits, integers, and double precision reals.   Sedgewick [Sed92] provides simple implementations of linear and additive congruential generators in C++. See Section gif for details.

XTango (see Section gif) is an algorithm animation system for UNIX and X-windows, which includes an animation illustrating the uniformity of random number generation.  

Notes: Knuth [Knu81] has a thorough and interesting discussion of random number generation, which I heartily recommend. He presents the theory behind several methods, including the middle square and shift-register methods we have not described here, as well as a detailed discussion of statistical tests for validating random number generators. Another good source is [PFTV86] - our recommended constants for the linear congruential generator are drawn from here. Comparisons of different random number generators in practice include [PM88].   

Tables of random numbers appear in most mathematical handbooks, as relics from the days before there was ready access to computers. Most notable is [RC55], which provides one million random digits.

The deep relationship between randomness, information, and compressibility is explored within the theory of Kolmogorov complexity, which measures the complexity of a string by its compressibility. Truly random strings are incompressible. The string of seemingly random digits of tex2html_wrap_inline27389 cannot be random under this definition, since the entire sequence is defined by any program implementing a series expansion for tex2html_wrap_inline27391 . Li and Vitáni [LV93] provide a thorough introduction to the theory of Kolmogorov complexity.    

Related Problems: Constrained and unconstrained optimization (see page gif), generating permutations (see page gif), generating subsets (see page gif), generating partitions (see page gif).        

next up previous contents index CD CD Algorithms
Next: Factoring and Primality Testing Up: Numerical Problems Previous: Linear Programming

Mon Jun 2 23:33:50 EDT 1997