3.2.1.3 POTENCY and this equation suggests (Web hosting comparison) that we
3.2.1.3 POTENCY and this equation suggests that we can avoid the multiplication; merely shifting and adding will suffice. For example, suppose that a = B2 + 1, where B is the byte size of MIX. The code LDA X SLA 2 ADD X (3) INCA I can be used in place of the instructions given in Section 3.2.1.1, and the execution time decreases from 1611 to 721. For this reason, multipliers having form (1) have been widely discussed in the literature, and indeed they have been recommended by many authors. However, the early years of experimentation with this method showed that multipliers having the simple form in (1) should be avoided. The generated numbers just aren t random enough. Later in this chapter we shall be discussing some rather sophisticated theory that accounts for the badness of all the linear congruential random number generators known to be bad. However, some generators (such as (2)) are suffi- ciently awful that a comparatively simple theory can be used to dispense with them. This simple theory is related to the concept of potency, which we shall now discuss. The potency of a linear congruential sequence with maximum period is defined to be the least integer s such that bS = 0 (modulo m). (4 (Such an integer s will always exist when the multiplier satisfies the conditions of Theorem 3.2.1.2A, since b is a multiple of every prime dividing m.) We may analyze the randomness of the sequence by taking X0 = 0, since 0 occurs somewhere in the period. With this assumption, we have x, = ((a -l)c/b) mod m, and if we expand an -1 = (b + l)n -1 by the binomial theorem, we find that All terms in bS, bs+l, etc., may be ignored, since they are multiples of m. Equation (5) can be instructive, so we shall consider some special cases. If a = 1, the potency is 1; and X, = cn (modulo m), as we have already observed, so the sequence is surely not random. If the potency is 2, we have X, G cn + cb(;), and again the sequence is not very random; indeed, X n+l-Xn=c+cbn