Sri lanka web server - 3.2.2 OTHER METHODS 29 Of course, the mere
3.2.2 OTHER METHODS 29 Of course, the mere fact that suitable constants al, . . . , uk exist giving a period of length pk -1 is not enough for practical purposes; we must be able to find them, and we can t simply try all p possibilities, since p is on the order of the computer s word size. Fortunately there are exactly p(pk -1)/k suitable choices of (al, . . . , ak), so there is a fairly good chance of hitting one after making a few random tries. But we also need a way to tell quickly whether or not (9) is a primitive polynomial modulo p; it is certainly unthinkable to generate up to p -1 elements of the sequence and wait for a repetition! Methods of testing for primitivity modulo p are discussed by Alanen and Knuth in Sankhya (A) 26 (1964), 305-328; the following criteria can be used: Let r = (pk - l)/(p -1). i) (-I) - ak must be a primitive root modulo p. (Cf. Section 3.2.1.2.) ii) The polynomial x7 must be congruent to (-l)k-lak, modulo f(x) and p. iii) The degree of 2 7/q mod f(z), using polynomial arithmetic modulo p, must be positive, for each prime divisor q of T. Efficient ways to compute the polynomial CP mod f(z), using polynomial arithmetic modulo a given prime p, are discussed in Section 4.6.2. In order to carry out this test, we need to know the prime factorization of T = (p -l)/(p -l), and this is the limiting factor in the calculation; T can be factored in a reasonable amount of time when k = 2, 3, and perhaps 4, but higher values of k are difficult to handle when p is large. Even k = 2 essentially doubles the number of significant random digits over what is achievable with k = 1, so larger values of k will rarely be necessary. An adaptation of the spectral test (Section 3.3.4) can be used to rate the sequence of numbers generated by (8); see exercise 3.3.4-26. The considerations of that section show that we should not make the obvious choice of al = j-1 or -1 when it is possible to do so; it is better to pick large, essentially random, values of al,…, ak that satisfy the conditions, and to verify the choice by applying the spectral test. A significant amount of computation is involved in finding al, . . . , ak, but all known evidence indicates that the result will be a very satisfactory source of random numbers. We essentially achieve the randomness of a linear congruential generator with k-tuple precision, using only single precision operations. The special case p = 2 is of independent interest. Sometimes a random number generator is desired that merely produces a random sequence of bits- zeros and ones-instead of fractions between zero and one. There is a simple way to generate a highly random bit sequence on a binary computer, manipulating k-bit words: Start with an arbitrary nonzero binary word X. To get the next random bit of the sequence, do the following operations, shown in MIX s language (see exercise 16): LDA X (Assume that overflow is now off. ) ADD X Shift left one bit. JNOV *+2 XOR A Jump if high bit was originally Otherwise adjust number with zero. exclusive or. (10) STA X I