Combined Linear Congruential Generator
A Combined Linear Congruential Generator (CLCG) is a pseudo-random number generator algorithm based on combining two or more linear congruential generators (LCG). A traditional LCG has a period which is inadequate for complex system simulation. By combining two or more LCGs, random numbers with a longer period and better statistical properties can be created. The algorithm is defined as:
- — the "modulus" of the first LCG
- — the ith input from the jth LCG
- — the ith generated random integer
where is a uniformly distributed random number between 0 and 1.
If Wi,1, Wi,2, ..., Wi,k are any independent, discrete, random-variables and one of them is uniformly distributed from 0 to m1 − 2, then Zi is uniformly distributed between 0 and m1 − 2, where:
Let Xi,1, Xi,2, ..., Xi,k be outputs from k LCGs. If Wi,j is defined as Xi,j − 1, then Wi,j will be approximately uniformly distributed from 0 to mj − 1. The coefficient "(−1)j−1" implicitly performs the subtraction of one from Xi,j.
The CLCG provides an efficient way to calculate pseudo-random numbers. The LCG algorithm is computationally inexpensive to use. The results of multiple LCG algorithms are combined through the CLCG algorithm to create pseudo-random numbers with a longer period than is achievable with the LCG method by itself.
The period of a CLCG is dependent on the seed value used to initiate the algorithm. The maximum period of a CLCG is defined by the function:
The following is an example algorithm designed for use in 32 bit computers:
LCGs are used with the following properties:
The CLCG algorithm is setup as follows:
1. The seed for the first LCG, , should be selected in the range of [1, 2,147,483,562].
- The seed for the second LCG, , should be selected in the range of [1, 2,147,483,398].
2. The two LCGs are evaluated as follows:
3. The CLCG equation is solved as shown below:
4. Calculate the random number:
5. Increment the counter (i=i+1) then return to step 2 and repeat.
The maximum period of the two LCGs used is calculated using the formula:.
This equates to 2.1x109 for the two LCGs used.
This CLCG shown in this example has a maximum period of:
This represents a tremendous improvement over the period of the individual LCGs. It can be seen that the combined method increases the period by 9 orders of magnitude.
Surprisingly the period of this CLCG may not be sufficient for all applications:. Other algorithms using the CLCG method have been used to create pseudo-random number generators with periods as long as 3x1057.
- Banks 2010, Sec. 7.3.2
- L'Ecuyer 1988
- Pandey 2008, Sec. 2.2
- L'Ecuyer 1996
- L'Ecuyer 1999
- L'Ecuyer 2002
- Banks, Jerry., Carson, John S., Nelson, Barry L., Nicol, David M., (2010). Discrete-Event System Simulation, 5th edition, Prentice Hall, ISBN 0-13-606212-1.
- P. L'Ecuyer (1988). "Efficient and Portable Combined Random Number Generators". Communications of the ACM 31: 742–749, 774. doi:10.1145/62959.62969.
- Pandey, Niraj. "IMPLEMENTATION OF LEAP AHEAD FUNCTION FOR LINEAR CONGRUENTIAL AND LAGGED FIBONACCI GENERATORS" (PDF). FLORIDA STATE UNIVERSITY. Retrieved 13 April 2012.
- P. L'Ecuyer (1996). "Combined Multiple Recursive Number Generators". Operations Research 44: 816–822. doi:10.1287/opre.44.5.816.
- P. L'Ecuyer (1999). "Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators". Operations Research 47: 159–164. doi:10.1287/opre.47.1.159.
- P. L'Ecuyer, R. Simard, E.J. Chen, W.D. Kelton (2002). "An Object-Oriented Randon-Number Package with Many Long Streams and Substreams". Operations Research 50: 1073–1075. doi:10.1287/opre.50.6.1073.358.