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 File:Hepa img871.gif 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.