|Summary of the book The Art of Computer Programming, Vol. 2, Chapter 3
Yu Zhang firstname.lastname@example.org
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.
Additive number generator and Lagged Fibonacci generators are other wildly used RNGs which generates purely additive or purely multiplicative sequences. Moreover, if we use general linear combinations of Xn-1, ..., Xn-k for small k, we can construct a kind of random number generators defined by . Here, we can set p as a large prime in order to get the best result. In this case, the period is pk-1. The inversive congruential method is an interesting generator. It defined by. There is another class of generators called combined generators. If people feel that the standard random number generators are too simple to generate random sequence, they can use this method to combine different simple random number generators.