Combined Linear Congruential Generator

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 ith input from the jth LCG
 X_i — the ith 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[edit]

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]

 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[edit]

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[edit]

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=40,014
m_1=2,147,483,563
a_2=40,692
m_2=2,147,483,399
c_1=c_2=0

The CLCG algorithm is setup as follows:

1. The seed for the first LCG,  Y_{0,1} , should be selected in the range of [1, 2,147,483,562].

The seed for the second LCG,  Y_{0,2} , should be selected in the range of [1, 2,147,483,398].
Set:  i=0

2. The two LCGs are evaluated as follows:

 Y_{i+1, 1} = 40,014 \times Y_{i,1}\pmod {2,147,483,563}
 Y_{i+1, 2} = 40,692 \times Y_{i,2}\pmod {2,147,483,399}

3. The CLCG equation is solved as shown below:

 X_{i+1}= (Y_{i+1, 1} - Y_{i+1, 2})\pmod{2,147,483,562}

4. Calculate the random number:

 R_{i+1} = \begin{cases}
  X_{i+1}/2,147,483,563 & \text{for }   X_{i+1} >  0 \\
  2,147,483,562/2,147,483,563 & \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.1x109 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 3x1057.[4][5][6]

See also[edit]

References[edit]

  1. ^ a b c d e f Banks 2010, Sec. 7.3.2
  2. ^ a b c d L'Ecuyer 1988
  3. ^ a b Pandey 2008, Sec. 2.2
  4. ^ L'Ecuyer 1996
  5. ^ L'Ecuyer 1999
  6. ^ L'Ecuyer 2002

External links[edit]