The code in this article uses a common type of random number generator known as the linear congruential generator (LCG). This generator produces random numbers based on the recursive formula
Zi = (aZi-1 + c)mod mwhere m > 0, 0 < a < m, 0 <= c < m, and 0= < Z(0) < m. In this formula, a is referred to as the multiplier and c as the increment. A good generator will produce each value in the range of 0 to m before a repeated value occurs. This behavior is referred to as full cycle generation. Of course, this algorithm, like any algorithm run on a computer, cannot generate truly random numbers. This becomes clear when you realize that every Z(i) can be determined from Z(0). However, through careful selection of m, a, and c, the numbers generated will appear to be independent and identically distributed. For an LCGto produce this sort of distribution, the following conditions must hold [2]:
1) The only positive integer that divides both m and c is 1.
2) If q is a prime number that divides m, then q divides a-1.
3) If 4 divides m, then 4 divides a-1.Consider the case of m = 8 and select a = 5, c = 3, and Z(0) = 5. The random number sequence generated would be 5, 4, 7, 6, 1, 0, 3, 2, 5.... Notice that each integer is generated once before the pattern restarts. The seed value determines the starting point in the pattern. In order to generate the variates in a different order either a, c, or both must be modified. Finally, observing the rules defined above does not guarantee that the generator will be statistically acceptable. See reference [1] for information on testing random number generators.
Multiplicative LCGs
The multiplicative LCG (MLCG) is a special case of the LCG for which the increment is assigned the value 0. Thus, the algorithm for random number generation becomes
Zi = (aZi-1)(mod m)To achieve a period of size m-1 for this algorithm, m must be a prime number. An MLCG based on a prime modulus is known as a PMMLCG (prime modulus MLCG).o