Pseudorandom Numbers

  Generated in a digital computer by a numerical algorithm, pseudorandom numbers are not random, but should appear to be random when used in Monte Carlo calculations ( Random Numbers).

The most widely used and best understood pseudorandom generator is the Lehmer multiplicative congruential generator, in which each number r is calculated as a function of the preceding number in the sequence:

or

where a and c are carefully chosen constants, and m is usually a power of two, 2^k. All quantities appearing in the formula (except m) are integers of k bits. The expression in brackets is an integer of length 2k bits, and the effect of the modulo is to mask off the most significant part of the result of the multiplication. r₀ is the seed of a generation sequence; many generators allow one to start with a different seed for each run of a program, to avoid re-generating the same sequence, or to preserve the seed at the end of one run for the beginning of a subsequent one. Before being used in calculations, the r_i are usually transformed to floating point numbers normalized into the range [0,1]. Generators of this type can be found which attain the maximum possible period of 2^k-2, and whose sequences pass all reasonable tests of ``randomness'', provided one does not exhaust more than a few percent of the full period ( [Knuth81]). A detailed discussion can be found in [Marsaglia85]. For portable generators, and many caveats concerning pseudorandom number generators, see [Press95].