Combined Linear Congruential Generator

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:

Z i = ( ∑ j = 1 k W i , j ) ( mod ( 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. The coefficient "(−1)^j−1" implicitly performs the subtraction of one from X_i,j.

Properties

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:

P = ( ( m 1 − 1 ) ( m 2 − 1 ) ⋯ ( m k − 1 ) ) / ( 2 k − 1 )

Example

The following is an example algorithm designed for use in 32 bit computers:

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 × Y i , 1 ( mod 2147483563 ) Y i + 1 , 2 = 40692 × Y i , 2 ( mod 2147483399 )

3. The CLCG equation is solved as shown below:

X i + 1 = ( Y i + 1 , 1 − Y i + 1 , 2 ) ( mod 2147483562 )

4. Calculate the random number:

R i + 1 = { X i + 1 / 2147483563 for  X i + 1 > 0 ( X i + 1 / 2147483563 ) + 1 for  X i + 1 < 0 2147483562 / 2147483563 for  X i + 1 = 0

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:.

( 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 × 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:. Other algorithms using the CLCG method have been used to create pseudo-random number generators with periods as long as 3x10⁵⁷.