3.2.1.2 CHOICE OF MULTIPLIER 15 3. [,%o] How (Web hosting company)
3.2.1.2 CHOICE OF MULTIPLIER 15 3. [,%o] How can the constant (w -1) be specified in general in the MIX assembly language, regardless of the value of the byte size? b 4. [Z] Discuss the calculation of linear congruential sequences with m = 232 on two s-complement machines such as the System/370 series. 5. [Zoo] Given that m is less than the word size, and that 2, y are nonnegative integers less than m, show that the difference (Z -y) mod m may be computed in just four MIX instructions, without requiring any division. What is the best code for the sum (x + y) mod m? b 6. [,%%I The previous exercise suggests that subtraction mod m is easier to perform than addition mod m. Discuss sequences generated by the rule Xn+l = (ax, -c) mod m. Are these sequences essentially different from linear congruential sequences as defined in the text? Are they more suited to efficient computer calculation? 7. [MzL$] What patterns can you spot in Table l? b 8. [.20] Write a MIX program analogous to (2) that computes (ax) mod (w -1). The values 0 and w -1 are to be treated as equivalent in the input and output of your program. 9. [~?3] Write a MIX program analogous to the one in exercise 8, but it should compute (ax) mod (w -2) . 3.2.1.2. Choice of multiplier. In this section we shall show how to choose the multiplier a so as to give the period of maximum length.. A long period is essential for any sequence that is to be used as a source of random numbers; indeed, we would hope that the period contains considerably more numbers than will ever be used in a single application. Therefore we shall concern ourselves in this section with the question of period length. The reader should keep in mind, however, that a long period is only one desirable criterion for the randomness of our sequence. For example, when a = c = 1, the sequence is simply X,+, = (X, + 1) mod m, and this obviously has a period of length m, yet it is anything but random. Other considerations affecting the choice of a multiplier will be given later in this chapter. Since only m different values are possible, the period surely cannot be longer than m. Can we achieve the maximum length, m? The example above shows that it is always possible, although the choice a = c = 1 does not yield a desirable sequence. Let us investigate all possible choices of a, c, and X0 that give a period of length m. It turns out that all such values of the parameters can be characterized very simply; when m is the product of distinct primes, only a = 1 will produce the full period, but when m is divisible by a high power of some prime there is considerable latitude in the choice of a. The following theorem makes it easy to tell if the maximum period is achieved.