Cool web site - 3.1 INTRODUCTION 5 K4. [Middle square.] Replace X
3.1 INTRODUCTION 5 K4. [Middle square.] Replace X by lX2/105] mod lOlo, i.e., by the middle of the square of X. K5. [Multiply.] Replace X by (1001001001 X) mod lOlo. K6. [Pseudo-complement.] If X < 100000000, then set X +- X + 9814055677; otherwise set X +- lOlo -X. K7. [Interchange halves.] Interchange the low-order five digits of X with the high-order five digits, i.e., X +- 105(X mod 105) + lX/105], the middle 10 digits of (lOlo + 1)X. K8. [Multiply.] Same as step K5. K9. [Decrease digits.] Decrease each nonzero digit of the decimal representation of X by one. K10. [99999 modify.] If X < 105, set X c X2 + 99999; otherwise set X t x -99999. Kll. [Normalize.] (At this point X cannot be zero.) If X < log, set X + 10X and repeat this step. K12. [Modified middle square.] Replace X by 1X(X -1)/105] mod lOlo, i.e., by the middle 10 digits of X(X -1). K13. [Repeat?] If Y > 0, decrease Y by 1 and return to step K2. If Y = 0, the algorithm terminates with X as the desired random value. I (The machine-language program corresponding to the above algorithm was in- tended to be so complicated that a person reading a listing of it without ex- planatory comments wouldn t know what the program was doing.) Considering all the contortions of Algorithm K, doesn t it seem plausible that it should produce almost an infinite supply of unbelievably random num- bers? No! In fact, when this algorithm was first put onto a computer, it almost immediately converged to the lO-digit value 6065038420, which-by extraordi- nary coincidence-is transformed into itself by the algorithm (see Table 1). With another starting number, the sequence began to repeat after 7401 values, in a cyclic period of length 3178. The moral of this story is that random numbers should not be generated with a method chosen at random. Some theory should be used. In this chapter, we shall consider random number generators that are su- perior to the middle-square method and to Algorithm K; the corresponding se- quences are guaranteed to have certain desirable random properties, and no degeneracy will occur. We shall explore the reasons for this random behavior in some detail, and we shall also consider techniques for manipulating random numbers. For example, one of our investigations will be the shuffling of a simu- lated deck of cards within a computer program. Section 3.6 summarizes this chapter and lists several bibliographic sources.