Summary of the book The Art of Computer Programming, Vol. 2, Chapter 3

This part of the book mainly talked about the classical random number generators. The author introduced the history of random number generate algorithms. Then, he presented many random number generators which are wildly used such as the linear congruential method, and analyzed their performance in detail.

Random numbers are wildly used in many different areas such as sampling, numerical analysis, etc. The earliest algorithm for generating random numbers is to take the digits of the square of the previous random number. But the sequences produced by this method always get into a short cycle of repeating digits. Then, the author came out algorithm K to generate random numbers. However, this method also has the above problem. In the following sections, the author stated many random number generators which have better performance than the two methods above.

The linear congruential method: In this method, the sequence is given by. When c=0, the speed is faster. But the length of the period of the sequence will become shorter. Fortunately, people proved that it still can make the period reasonably long. When c=0, this kind of method has a term multiplicative congruential method. When c!=0, it is called mixed congruential method. The author also proved that in order to get the maximum period m, the parameters should meet the following conditions: (1) c is relatively prime to m; (2) for every prime number dividing m, b = a-1 is a multiple of this number; (3) b is a multiple of 4, if m is a multiple of 4. This method can be generalized to a method called a quadratic congruential method: . This algorithm also can meet the maximum period length.