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]

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

where:

${\displaystyle m_{1}}$ — the "modulus" of the first LCG
${\displaystyle Y_{i,j}}$ — the ith input from the jth LCG
${\displaystyle X_{i}}$ — the ith generated random integer

with:

${\displaystyle 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 ${\displaystyle R_{i}}$ is a uniformly distributed random number between 0 and 1.

Derivation

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:[2]

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

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.[2] The coefficient "(−1)j−1" implicitly performs the subtraction of one from Xi,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]

${\displaystyle 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]

${\displaystyle 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}$
${\displaystyle c_{1}=c_{2}=0}$

The CLCG algorithm is set up as follows:

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

The seed for the second LCG, ${\displaystyle Y_{0,2}}$, should be selected in the range of [1, 2147483398].
Set: ${\displaystyle 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]

${\displaystyle (m-1)}$

This equates to 2.1x109 for the two LCGs used.

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

${\displaystyle (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 3x1057.[4][5][6]