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:

a_{1}=40014

m_{1}=2147483563

a_{2}=40692

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:

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

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

3. The CLCG equation is solved as shown below:

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

4. Calculate the random number:

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]

References

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

External links

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

This article is issued from Wikipedia - version of the 5/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.