Cheapest web hosting - 3.2.2 OTHER METHODS 27 where m is even,
3.2.2 OTHER METHODS 27 where m is even, and where X0, . . . ,X54 are arbitrary integers not all even. The constants 24 and 55 in this definition were not chosen at random, they are special values that happen to have the property that the least significant bits (X, mod 2) will have a period of length 255 -1. Therefore the sequence (Xn) must have a period at least this long. Exercise 11, which explains how to calculate the period length of such sequences, proves that (7) has a period of length 2f(255 -1) for some f, 0 2 f < e, when m = 2=. At first glance Eq. (7) may not seem to be extremely well suited to machine implementation, but in fact there is a very efficient way to generate the sequence using a cyclic list: Algorithm A (Additive number generator). Memory cells Y[l], Y[2], . . . , Y[55] are initially set to the values X54, X53, . . . , X0, respectively; j is initially equal to 24 and k is 55. Successive performances of this algorithm will produce the numbers X55, X56, . . . as output. Al. [Add.] (If we are about to output X, at this point, Y[j] now equals X+-24 andY[k] equalsXn-55.) Set Y[k] t (Y[k]+Y[j])mod2 , andoutputY[k]. A2. [Advance.] Decrease j and k by 1. If now j = 0, set j +- 55; otherwise if k = 0, set k c 55. 1 This algorithm in MIX is simply the following: Program A (Additive number generator). Assuming that index registers 5 and 6 are not touched by the remainder of the program in which this routine is embedded, the following code performs Algorithm A and leaves the result in register A. r15 = j, r16 = k. LDA Y,6 Al. Add. ADD Y, 5 Yk + Y, (overflow possible) STA Y,6 + Yk. DEC5 1 A2. Advance. j t j -1. DEC6 1 ktk-1. J5P *+ 2 ENT5 55 If j = 0, set j t 55. J6P *+ 2 ENT6 55 If k = 0, set k + 55. 1 This generator is usually faster than the previous methods we have been discussing, since it does not require any multiplication. Besides its speed, it has the longest period we have seen yet; and it has consistently produced reliable results, in extensive tests since its invention in 1958. Furthermore, as Richard Brent has observed, it can be made to work correctly with floating point numbers, avoiding the need to convert between integers and fractions (cf. exercise 23). Therefore it may well prove to be the very best source of random numbers for practical purposes. The only reason it is difficult to recommend sequence (7) wholeheartedly is that there is still very little theory to prove that it does or does not have desirable randomness properties; essentially all we know for sure