14 RANDOMNUMBERS 3.2.1.1 the numbers Y, = X,
14 RANDOMNUMBERS 3.2.1.1 the numbers Y, = X, mod24. The gist of Eq. (4) is that the low-order four bits of (Xn) form a congruential sequence that has a period of length 16 or less. Similarly, the low-order five bits are periodic with a period of at most 32; and the least significant bit of X, is either constant or strictly alternating. This situation does not occur when m = w f 1; in such a case, the low-order bits of X, will behave just as randomly as the high-order bits do. If, for example, w = 235 and m = 235 - 1, the numbers of the sequence will not be very random if we consider only their remainders mod 31, 71, 127, or 122921 (cf. Table 1); but the low-order bit, which represents the numbers of the sequence taken mod 2, would be satisfactorily random. Another alternative is to let m be the largest prime number less than w. This prime may be found by using the techniques of Section 4.5.4, and a table of suitably large primes appears in that section. In most applications, the low-order bits are insignificant, and the choice m = w is quite satisfactory-provided that the programmer using the random numbers does so wisely. Our discussion so far has been based on a signed magnitude computer like MIX. Similar ideas apply to machines that use complement notations, although there are some instructive variations. For example, a DEC 20 computer has 36 bits with two s complement arithmetic; when it computes the product of two nonnegative integers, the lower half contains the least significant 35 bits with a plus sign. On this machine we should therefore take w = 235, not 236. The 32-bit two s complement arithmetic on IBM System/370 computers is different: the lower half of a product contains a full 32 bits. Some programmers have felt that this is a disadvantage, since the lower half can be negative when the operands are positive, and it is a nuisance to correct this; but actually it is a distinct advantage from the standpoint of random number generation, since we can take m = 232 instead of 231 (see exercise 4). EXERCISES 1. [MLZ] In exercise 3.2.1-3 we concluded that the best congruential generators will have the multiplier a relatively prime to m. Show that when m = w in this case it is possible to compute (ax + c)modw in just three MIX instructions, rather than the four in (1) with the result appearing in register X. 2. [16] Write a MIX subroutine having the following characteristics: Calling sequence: JMP RANDM Entry conditions: Location XRAND contains an integer x. Exit conditions: X + rA + (ax + c) mod 20, rX t 0, overflow off. (Thus a call on this subroutine will produce the next random number of a linear congruential sequence.)