3.2.1.1 CHOICE OF MODULUS 11 b 2. [M.zo] (Web site counters)
3.2.1.1 CHOICE OF MODULUS 11 b 2. [M.zo] Show that if a and m are relatively prime, the number X0 will always appear in the period. 3. [Ml01 If a and m are not relatively prime, explain why the sequence will be somewhat handicapped and probably not very random; hence we will generally want the multiplier a to be relatively prime to the modulus m. 4. [II] Prove Eq. (6). 5. [M?O] Equation (6) holds for k > 0. If possible, give a formula that expresses Xn+k in terms of X, for negative values of k. 3.2.1.1. Choice of modulus. Our current goal is to find good values for the parameters that define a linear congruential sequence. Let us first consider the proper choice of the number m. We want m to be rather large, since the period cannot have more than m elements. (Even if a person wants to generate only random zeros and ones, he should not take m = 2, for then the sequence would at best have the form. . . , 0, 1, 0, 1, 0, 1, . . . ! Methods for modifying random numbers to get random zeros and ones are discussed in Section 3.4. ) Another factor that influences our choice of m is speed of generation: We want to pick a value so that the computation of (ax, + c) mod m is fast. Consider MIX as an example. We can compute ymod m by putting y in registers A and X and dividing by m; assuming that y and m are positive, we see that y mod m will then appear in register X. But division is a comparatively slow operation, and it can be avoided if we take m to be a value that is especially s convenient, such as the word size of our computer. Let w be the computer s word size, namely, 2e on an e-bit binary computer or 10e on an e-digit decimal machine. (In this book we shall often use the letter e to denote an arbitrary integer exponent, instead of the base of natural logarithms, hoping that the context will make our notation unambiguous. Physicists have a similar problem when they use e for the charge on an electron.) The result of an addition operation is usually given modulo w, except on ones -complement machines; and multiplication mod w is also quite simple, since the desired result is the lower half of the product. Thus, the following program computes the quantity (ax + c) mod w efficiently: LDA A rA + a. MUL X rAX + (rA).X. SLAX 5 rA t rAXmodw. (1) ADD C rAt(rA+c)modw. m The result appears in register A. The overflow toggle might be on at the conclu- sion of the above sequence of instructions, and if this is undesirable, the code should be followed by, e.g., JOV *+l to turn it off. A clever technique that is less commonly known can be used to perform computations modulo (w + 1). For reasons to be explained later, we will generally want c = 0 when m = w + 1, so we merely need to compute (ax) mod (w + 1).