Random Numbers

where we have made explicit only the dependence on the immediate predecessor. The most important representatives of this class of generators are the

• linear congurential,
• lagged Fibonacci,
• shift-register, or a
• combination of linear congurential.

For the moment we consider such generator functions G that produce numbers in the interval between zero and one with a uniform distribution.

A very simple generator is constructed using the modulo function

This function produces a dilatation, translation and a folding back into the interval. Random number generators based on this function are called linear congurential generators or LCG(a,b,M) for short. If we assume integers as the set on which the modulo function is defined, then for example, the range of integer numbers for a 32-bit architecture is at most M = 2³¹-1. Here we assume that one bit is taken for the sign of the number. Then the numbers range at most from 0 to M-1. Of course we can map these onto the real interval between 0 and 1, recognizing that this is an approximation to the real-valued random numbers.

The choice of the parameters a, b and M determine the statistical properties and how many different numbers we can expect before the sequence repeats itself. The period can be shown to be maximal, if M is chosen to be a prime number. Then the whole range of numbers occurs. That the period be as large as possible is immediately evident if we consider that large simulations are possible, using systems with more than 1000³ entities. A conventional modulo generator can at most produce M = 2³¹-1 random numbers. Hence one sweep exhausts all random numbers!