next up previous

Example 3 LCG (5, 0, 37, 1)

We obtain the sequence
1,5,25,14,33,17,11,18,16,6,30,2,10,13,28,29,34,22, 36,32,12,23,4,20,26,19,21,31,7,35,27,24,9,8,3,15, Table 3 provides the sequence throughout the period. Here, because we use a prime number as the divisor for the modulus operation and c = 0, we obtain a period one less than modulus 37 (0 is not possible, as it maps to itself, so we obtain a period of 36). Indeed, when m = p, a prime, the maximum period, , is m-1, even if . Thus, for linear, congruential generators with a prime modulus, using a non-zero c does not increase the period.

Here, the low order bits, while not exhibiting a discernible pattern, do not appear as ``random'' as one might expect. Indeed, as is shown in Altman [1], the bitwise randomness properties of LCGs should be considered on a case by case basis. He provides examples of LCGs with prime moduli that fail bitwise testing, but points out, for example, that does pass the bitwise randomness test.

Table 3a: Random Sequence of Example 3 - LCG (5, 0, 37, 1) (part 1).

Table 3b: Random Sequence of Example 3 - LCG (5, 0, 37, 1) (part 2).

(See exercise 8.)