Pseudo-numbers  (Page 2/2)

Fortunately, one a value of the m has been selected; theoretical results exist that give conditions for choosing values of the multiplier a and the additive constant c such that all the possible integers, 0 through $m-1$ , are generated before any are repeated.

THEOREM I

A linear congruential generator will have maximal cycle length m , if and only if:

• c is nonzero and is relatively prime to m (i.e., c and m have no common prime factors).
• $\left(a\mathrm{mod}q\right)=1$ for each prime factor q of m .
• $\left(a\mathrm{mod}4\right)=1$ if 4 is a factor of m .

PROOF

As a mathematical note, c is called relatively prime to m if and only if c and m have no common divisor other than 1, which is equivalent to c and m having no common prime factor.

A related result concerns the case of c chosen to be 0. This case does not conform to condition in a Theorem I , a value $U_i$ of zero must be avoided because the generator will continue to produce zero after the first occurrence of a zero. In particular, a seed of zero is not allowable. By Theorem I , a generator with $c=0$ , which is called a multiplicative congruential generator , cannot have maximal cycle length m . However, By Theorem II . It can have cycle length $m-1$ .

THEOREM II

If $c=0$ in a linear congruential generator, then $U_i=0$ can never be included in a cycle, since the 0 will always repeat. However, the generator will cycle through all $m-1$ integers in the set $\left(a\mathrm{mod}q\right)$ if and only if:

• m is a prime integer and
• m is a primitive element modulo m .

PROOF

A formal definition or primitive elements modulo m , as well as theoretical results for finding them, are given in Knuth (1981) . In effect, when m is a prime, a is a primitive element if the cycle is of length $m-1$ . The results of Theorem II are not intuitively useful, but for our purposes, it is enough to note that such primitive elements exist and have veen computed by researchers,

• Choose a , c , and m according to Theorem I and work with a generator whose cycle length is known to be m .
• Choose $c=0$ , take a and m according to Theorem II , use a number other than zero as the seed, and work with a generator whose cycle length is known to be $m-1$ . A generator satisfying these conditions is known as a prime-modulus multiplicative congruential generator and, because of the simpler computation, it usually has an advantage in terms of speed over the mixed congruential generator.

Another method frequency speeding up a random number generator that has $c=0$ is to choose the modulus m to be computationally convenient. For instance, consider $m=2^k.$ This is clearly not a prime number, but on a computer the modulus operation becomes a bit-shift operation in machine code. In such cases, Theorem III gives a guise to the maximal cycle length.

THEOREM III

If $c=0$ and $m=2^k$ with $k>2$ , then the maximal possible cycle length is $2^{k-2}$ . This is achieved if and only if two conditions hold:

• a is a primitive element modulo m .
• the seed is odd.

PROOF

Notice that we sacrifice some of the cycle length and, as we will se in Theorem IV, we also lose some randomness in the low-order bits of the random variates. Having use any of Theorems I , II , or III to select triples ( a, c, m ) that lead to generators with sufficiently long cycles of known length, we can ask which triple gives the most random (i.e., approximately independent ) sequence. Although some theoretical results exist for generators as a whole, these are generally too weak to eliminate any but the worst generators. Marsaglia (1985) and Knuth(1981, Chap. 3.3.3) are good sources for material on that results.

THEOREM IV

If $U_i=a{U}_{i-1}\mathrm{mod}{2}^k$ , and we define

PROOF

Such normal behavior in the low-order bits of a congruential generator with non-prime-modulus m is an undesirably property, which may be aggravated by techniques such as the recycling of uniform variates. It has been observed (Hutchinson, 1966) that prime-modulus multiplicative congruential generators with full cycle (i.e., when m is a positive primitive element) tend to have fairly randomly distributed low-order bits, although no theory exists to explain this.

THEOREM V

If our congruential generator produces the sequence $\left(U_1,U_2\mathrm{,...}\right)$ , and we look at the following sequence of points in n dimensions:

PROOF

Given these known limitations of congruential generator, we are still left with the question of how to choose the “best” values for a , c , and m . To do this, researchers have followed a straightforward but time-consuming procedure:

• Take values a , c , and m that give a sufficiently long, known cycle length and usa the generator to produce sequences of uniform variates.
• Subject the output sequences to batteries of statistical tests for independence and a uniform marginal distribution. Document the results.
• Subject the generator to theoretical tests. In particular, the spectral test of Coveyou and MacPherson (1967) is currently widely used and recognized as a very sensitive structural test for distinguishing between good and bad generators. Document the results.
• As new, more sensitive tests appear, subject to generator to those tests. Several such tests are discussed in Marsaglia(1985) .