The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.2.7 Random Number Generation

Problem Input | Problem Output

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.


Implementations

  • Random Number Generation using Shift Register and Quasi method (C++,C,FORTRAN,ADA) (rating 8)
  • NIST statistical test suite (C) (rating 8)
  • Parallel Random Number Generation (C++,C,Java) (rating 8)
  • SPRNG:The Scalable Parallel Random Number Generators Library (C++, C, FORTRAN) (rating 8)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
  • Pseudo random number generators (C++) (rating 5)

  • Recommended Books

    Automatic Nonuniform Random Variate Generation by W. H"{o Random Number Generation and Monte Carlo Methods by J. Gentle Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky
    An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul M. B. Vitanyi A million random digits with 100,000 normal deviates by Rand-Corporation

    Related Links

  • pLab: random number generator page
  • True Random Number Service (from atmospheric noise)

    Related Problems


      
    Generating Partitions
      
    Generating Permutations
      
    Generating Subsets
      
    Constrained and Unconstrained Optimization



    This page last modified on 2008-07-10 .
    www.algorist.com