Best web hosting site - 28 RANDOM NUMBERS 3.2.2 Table 1 SUBSCRIPT PAIRS
28 RANDOM NUMBERS 3.2.2 Table 1 SUBSCRIPT PAIRS MELDING LONG PERIODS MOD (1, 2) (1, 15) (5, 23) (7, 31) (5, 47) (21, 52) (18, 65) (28, 73) (2, 93) (1, 3) (4, 15) (9, 23) (13, 31) (14, 47) (24, 55) (32, 65) (31, 73) (21, 94) (1, 4) (7, 15) (3, 25) (13, 33) (20, 47) (7, 57) (9, 68) (9, 79) (11, 95) (2, 5) (3, 17) (7, 25) (2, 35) (21, 47) (22, 57) (33, 68) (19, 79) (17, 95) (1, 6) (5, 17) (3, 28) (11, 36) (9, 49) (19, 58) (6, 71) (4, 81) (6, 97) (1, 7) (6, 17) (9, 28) (4, 39) (12, 49) (1, 60) (9, 71) (16, 81) (12, 97) (3, 7) (7, 18) (13, 28) (8, 39) (15, 49) (11, 60) (18, 71) (35, 81) (33, 97) (4, 9) (3, 20) (2, 29) (14, 39) (22, 49) (1, 63) (20, 71) (13, 84) (34, 97) (3, 10) (2, 21) (3, 31) (3, 41) (3, 52) (5, 63) (35, 71) (13, 87) (11, 98) (2, 11) (1, 22) (6, 31) (20, 41) (19, 52) (31, 63) (25, 73) (38, 89) (27, 98) For each pair (1, k), the pair (k–l, k) is also valid (see exercise 24), hence only values of 1 5 k/2 are listed here. For extensions of this table, see N. Zierler and J. Brillhart, Information and Control 13 (1968), 541-554; 14 (1969), 566-569; 15 (1969), 67-69. is that the period is very long, and this is not enough. John Reiser (Ph. D. thesis, Stanford Univ., 1977) has shown, however, that an additive sequence like (7) will be well distributed in high dimensions, provided that a certain plausible conjecture is true (cf. exercise 26). The fact that the special numbers (24, 55) in (7) work so well follows from theoretical results developed in some of the exercises below. Table 1 lists all pairs (I, k) for which the sequence X, = (X,-l +X+-k) mod 2 has period length 2k -1, when Ic < 100. The pairs (1, Ic) for small as well as larger k are shown, for the sake of completeness; the pair (1, 2) corresponds to the Fibonacci sequence mod 2, whose period has length 3. However, only pairs (1, k) for relatively large k should be used to generate random numbers in practice. Instead of considering only additive sequences, we can construct useful ran- dom number generators by taking general linear combinations of Xn-i, . . . , Xn-k for small k. In this case the best results occur when the modulus m is a large prime; for example, m can be chosen to be the largest prime number that fits in a single computer word (see Table 4.5.4-l). When m I= p is prime, the theory of finite fields tells us that it is possible to find multipliers al, . . . , ok such that the sequence defined by x, = (al&-1 + * * * + &&+k) modp (8) has period length pk - 1; here Xc, . . . ,Xk-r may be chosen arbitrarily but not all zero. (The special case k = 1 corresponds to a multiplicative congruential sequence with prime modulus, with which we are already familiar.) The constants al,…, ak in (8) have the desired property if and only if the polynomial f(x) = xk -al+-1 -. . . - ak (9) is a primitive polynomial modulo p, that is, if and only if this polynomial has a root that is a primitive element of the field with p elements (see exercise 4.6.2-16).