12 RANDOM NUMBERS 3.2.1.1 (Simple web server) The following program does
12 RANDOM NUMBERS 3.2.1.1 The following program does this: 01 LDAN X rA + -X. 02 MUL A rAX t @A). a. 03 STX TEMP 04 SUB TEMP rA+rA-rX. ( 4 05 JANN *+3 Exit if rA > 0. 06 INCA 2 rA+rA+2. 07 ADD =w -1= rA + rA f w -1. (Cf. exercise 3.) 1 Register A now contains the value (ax) mod (W + 1). Of course, this value might lie anywhere between 0 and w, inclusive, so the reader may legitimately wonder how we can represent so many values in the A-register! (The register obviously cannot hold a number larger than w -1.) The answer is that overflow will be on after the above program if and only if the result equals w, assuming that overflow was initially off. It is convenient simply to reject the value w if it appears in the congruential sequence modulo w + 1; this will happen if lines 05 and 06 of (2) are replaced by JANN ++4; INCA 2; JAP *-5 . To prove that code (2) actually does determine (a~) mod (w + l), note that in line 04 we are subtracting the lower half of the product from the upper half. No overflow can occur at this step; and if aX = qw + r, with 0 2 r < w, we will have the quantity r -q in register A after line 04. Now ax = q(w + 1) + (r - 91, and since q < w, we have -w < r -q < w; hence (ax) mod(w + 1) equals either r -q or r -q + (w + l), depending on whether r -q 2 0 or r -q < 0. A similar technique can be used to get the product of two numbers modulo (w -1); see exercise 8. In later sections we shall require a knowledge of the prime factors of m in order to choose the multiplier a correctly. Table 1 lists the complete factorization of w f 1 into primes for nearly every known computer word size; the methods of Section 4.5.4 can be used to extend this table if desired. The reader may well ask why we bother to consider using m = w f 1, when the choice m = w is so manifestly convenient. The reason is t,hat when m = w, the right-hand digits of X, are much less random than the left-hand digits. If d is a divisor of m. and if Y, = X, mod d, (3) we can easily show that Yn+l = (aY, + c) mod d. (4 (For, Xn+l = ax, + c - qm for some integer q, and taking both sides mod d causes the quantity qm to drop out when d is a factor of m.) To illustrate the significance of Eq. (4), let us suppose, for example, that we have a binary computer. If m = 20 = 2e, the low-order four bits of X, are