30 RANDOM NUMBERS 3.2.2 The (Business web hosting) fourth instruction here
30 RANDOM NUMBERS 3.2.2 The fourth instruction here is the exclusive or operation found on nearly all binary computers (cf. exercise 2.5-28 and Section 7.1); it changes each bit position in which location A has a 1 bit. The value in location A is the binary - constant (al . . . uk)~, where xk -alx k–l . . . - ak is a primitive polynomial modulo 2 as above. After the code (10) has been executed, the next bit of the generated sequence may be taken as the least significant bit of word X (or, alternatively, we could consistently use the most significant bit of X, if it were more convenient to do so). For example, consider Fig. 1, which illustrates the sequence generated for Ic = 4 and CONTENTS(A) = (0011)~. This is, of course, an unusually small value for k. The right-hand column shows the sequence of bits of the sequence, namely 1101011110001001.. . , repeating in a period of length 2k - 1 = 15. This sequence is quite random, considering that it was generated with only four bits of memory; to see this, consider the adjacent sets of four bits occurring in the period, namely 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0001, 0010, 0100, 1001, 0011, 0110. In general, every possible adjacent set of Ic bits occurs exactly once in the period, except the set of all zeros, since the period length is 2k - 1; thus, adjacent sets of Ic bits are essentially independent. We shall see in Section 3.5 that this is a very strong criterion for randomness when Ic is, say, 30 or more. Theoretical results illustrating the randomness of this sequence are given in an article by R. C. Tausworthe, Math. Comp. 19 (1965), 201-209. Primitive polynomials modulo 2 of degree 5 100 have been tabulated by E. J. Watson, Math. Comp. 16 (1962), 368-369. When k = 35, we may take CONTENTS(A) = (OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOlOl)~, but the considerations of exercises 18 and 3.3.4-26 imply that it would be better to find random constants that define primitive polynomials modulo 2. Caution: Several people have been trapped into believing that this random bit-generation technique can be used to generate random whole-word fractions (.X0X1 . . . xk-112, (.xkxk+l . . .X2k-1)2, . . . ; but it is actually a poor source of random fractions, even though the bits are individually quite random. Exercise 18 explains why. Mitchell and Moore s additive generator (7) is essentially based on the con- cept of primitive polynomials; the polynomial x55 + x24 + 1 is primitive, and Table 1 is essentially a listing of all the primitive trinomials modulo 2. A generator almost identical to that of Mitchell and Moore was independently dis- covered in 1971 by T. G. Lewis and W. H. Payne [cf. JACM 20 (1973), 456-4681, but using exclusive or instead of addition so that the period is exactly 255 - 1; each bit position in their generated numbers runs through the same periodic sequence, but has its own starting point. (See Bright and Enison, Computing Surveys 11 (1979), 357-370, for further discussion of Lewis and Payne s method.) We have now seen that sequences with 0 2 X, < m and period mk -1 can be found, when X, is a suitable function of X,-l, . . . ,X+.-k and when m is prime. The highest conceivable period for any sequence defined by a relation