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.^[1] By combining two or more LCGs, random numbers with a longer period and better statistical properties can be created.^[1] The algorithm is defined as:^[2]

$X_{i}\equiv \left(\sum _{{j=1}}^{k}(-1)^{{j-1}}Y_{{i,j}}\right){\pmod {(m_{1}-1)}}$

where:

$m_{1}$ — the "modulus" of the first LCG

$Y_{{i,j}}$ — the i^th input from the j^th LCG

$X_{i}$ — the i^th generated random integer

with:

$R_{i}\equiv {\begin{cases}X_{i}/m_{1}&{\text{for }}X_{i}>0\\(m_{1}-1)/m_{1}&{\text{for }}X_{i}=0\end{cases}}$

where $R_{i}$ is a uniformly distributed random number between 0 and 1.

Derivation

If W_i,1, W_i,2, ..., W_i,k are any independent, discrete, random-variables and one of them is uniformly distributed from 0 to m₁ − 2, then Z_i is uniformly distributed between 0 and m₁ − 2, where:^[2]

$Z_{i}=\left(\sum _{{j=1}}^{k}W_{{i,j}}\right){\pmod {(m_{1}-1)}}$

Let X_i,1, X_i,2, ..., X_i,k be outputs from k LCGs. If W_i,j is defined as X_i,j − 1, then W_i,j will be approximately uniformly distributed from 0 to m_j − 1.^[2] The coefficient "(−1)^j−1" implicitly performs the subtraction of one from X_i,j.^[1]

Properties

The CLCG provides an efficient way to calculate pseudo-random numbers. The LCG algorithm is computationally inexpensive to use.^[3] 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.^[3]

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:^[1]

$P=((m_{1}-1)(m_{2}-1)\cdots (m_{k}-1))/(2^{{k-1}})$

Example

The following is an example algorithm designed for use in 32 bit computers:^[2]

$k=2$

LCGs are used with the following properties:

${\displaystyle a_{1}=40014}$

${\displaystyle m_{1}=2147483563}$

${\displaystyle a_{2}=40692}$

${\displaystyle m_{2}=2147483399}$

$c_{1}=c_{2}=0$

The CLCG algorithm is set up as follows:

1. The seed for the first LCG, $Y_{{0,1}}$, should be selected in the range of [1, 2147483562].

The seed for the second LCG, $Y_{{0,2}}$, should be selected in the range of [1, 2147483398].

Set: $i=0$

2. The two LCGs are evaluated as follows:

${\displaystyle Y_{i+1,1}=40014\times Y_{i,1}{\pmod {2147483563}}}$

${\displaystyle Y_{i+1,2}=40692\times Y_{i,2}{\pmod {2147483399}}}$

3. The CLCG equation is solved as shown below:

${\displaystyle X_{i+1}=(Y_{i+1,1}-Y_{i+1,2}){\pmod {2147483562}}}$

4. Calculate the random number:

${\displaystyle R_{i+1}={\begin{cases}X_{i+1}/2147483563&{\text{for }}X_{i+1}>0\\(X_{i+1}/2147483563)+1&{\text{for }}X_{i+1}<0\\2147483562/2147483563&{\text{for }}X_{i+1}=0\end{cases}}}$

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:.^[1]

$(m-1)$

This equates to 2.1x10⁹ for the two LCGs used.

This CLCG shown in this example has a maximum period of:

$(m_{1}-1)(m_{2}-1)/2=2.3\times 10^{{18}}$

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:.^[1] Other algorithms using the CLCG method have been used to create pseudo-random number generators with periods as long as 3x10⁵⁷.^[4][5][6]

See also

• Linear congruential generator

References

1. Banks 2010, Sec. 7.3.2
2. L'Ecuyer 1988
3. Pandey 2008, Sec. 2.2
4. L'Ecuyer 1996
5. L'Ecuyer 1999
6. 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.

External links

• An overview of use and testing of pseudo-random number generators