1.2.7 Random Number Generation
INPUT OUTPUT
Input Description:
Nothing, or perhaps a seed.
Problem:
Generate a sequence of random integers.
Excerpt from
The Algorithm Design Manual:
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.
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.
Recommended Books
Related Links
pLab: random number generator page
True Random Number Service (from atmospheric noise)
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Automatic Nonuniform Random Variate Generation
Random Number Generation and Monte Carlo Methods
Algorithms in Java, Third Edition (Parts 1-4)
An Introduction to Kolmogorov Complexity and Its Applications
A million random digits with 100,000 normal deviates
