Top Previous Next

3. Random number generators (RNGs)

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.
John von Neumann, 1951

Pseudo RNG

An RNG is an algorithm that produces series of random numbers. The series is not really random: pseudo. The algorithm is deterministic; the same input will always generate the same output.

Seed

The input can be varied: the seed. Different seeds should ideally generate totally uncorrelated series. One may choose a seed manually, or use the current time, or some other variable value.

Output interval

Uniform RNGs: within a range [0, MAXINT] every value has the same probability of being produced next.

Integers vs real numbers (continuous). Open or closed intervals:

Period (cycle)

An RNG has a period (cycle). After some (hopefully large) M number of random numbers have been produced, the RNG will loop back to where the series started.

The current consensus is that any simulation should use only a small fraction (< 1%) of the values available in the period for an RNG. So the period should be very large.

Randomness; quality

How characterize? How measure quality, or test? Look out for pathological cases, subtle correlations, non-uniform distributions. Many theoretical and numerical tests available, but none can ever prove that an RNG is perfect.

Warning: Low-order bits are often bad. Do not use.

Basic message: some RNGs are known to be bad, others have passes many tests successfully. No proof, though. Use several different RNGs for solving your problem when the result depends critically on the RNG quality, as they sometimes do in simulations of various natural processes.


Copyright © 2000 Per Kraulis $Date: 2000/12/12 15:51:51 $