Misplaced Pages

Combined linear congruential generator

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Pseudo-random number generator algorithm

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. By combining two or more LCGs, random numbers with a longer period and better statistical properties can be created. The algorithm is defined as: X i ≡ ( ∑ j = 1 k ( − 1 ) j − 1 Y i , j ) ( mod m 1 − 1 ) {\displaystyle X_{i}\equiv \left(\sum _{j=1}^{k}(-1)^{j-1}Y_{i,j}\right){\pmod {m_{1}-1}}} where:

  • m 1 {\displaystyle m_{1}} is the "modulus" of the first LCG
  • Y i , j {\displaystyle Y_{i,j}} is the i input from the j LCG
  • X i {\displaystyle X_{i}} is the i generated random integer

with: R i ≡ { X i / m 1 for  X i > 0 ( m 1 − 1 ) / m 1 for  X i = 0 {\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 R i {\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: Z i = ( ∑ j = 1 k W i , j ) ( mod m 1 − 1 ) {\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. The coefficient "(−1)" implicitly performs the subtraction of one from Xi,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 the least common multiple of the periods of the individual generators, which are one less than the moduli. Since all the moduli are odd primes, the periods are even and thus share at least a common divisor of 2, but if the moduli are chosen so that 2 is the greatest common divisor of each pair, this will result in a period of: P = ( m 1 − 1 ) ( m 2 − 1 ) ⋯ ( m k − 1 ) 2 k − 1 {\displaystyle P={\frac {(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: k = 2 {\displaystyle k=2} LCGs are used with the following properties: a 1 = 40014 a 2 = 40692 m 1 = 2147483563 m 2 = 2147483399 c 1 = 0 c 2 = 0 {\displaystyle {\begin{aligned}a_{1}&=40014&a_{2}&=40692\\m_{1}&=2147483563&m_{2}&=2147483399\\c_{1}&=0&c_{2}&=0\end{aligned}}}

The CLCG algorithm is set up as follows:

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

    The seed for the second LCG, Y 0 , 2 {\displaystyle Y_{0,2}} , should be selected in the range of .

    Set: i = 0 {\displaystyle i=0}
  2. The two LCGs are evaluated as follows: Y i + 1 , 1 = 40014 × Y i , 1 ( mod 2147483563 ) {\displaystyle Y_{i+1,1}=40014\times Y_{i,1}{\pmod {2147483563}}} Y i + 1 , 2 = 40692 × Y i , 2 ( mod 2147483399 ) {\displaystyle 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 ) ( mod 2147483563 ) {\displaystyle X_{i+1}=(Y_{i+1,1}-Y_{i+1,2}){\pmod {2147483563}}}
  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 {\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: ( m − 1 ) {\displaystyle (m-1)} This equates to 2.1×10 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 {\displaystyle (m_{1}-1)(m_{2}-1)/2\approx 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. Other algorithms using the CLCG method have been used to create pseudo-random number generators with periods as long as 3×10.

The former of the two generators, using b = 40,014 and m = 2,147,483,563, is also used by the Texas Instruments TI-30X IIS scientific calculator.

See also

References

  1. ^ Banks, Jerry; Carson, John S.; Nelson, Barry L.; Nicol, David M. (2010). Discrete-Event System Simulation (5th ed.). Prentice Hall. § 7.3.2. ISBN 978-0-13-606212-7.
  2. ^ L'Ecuyer, Pierre (1988). "Efficient and Portable Combined Random Number Generators" (PDF). Communications of the ACM. 31 (6): 742–749, 774. CiteSeerX 10.1.1.72.88. doi:10.1145/62959.62969. S2CID 9593394.
  3. ^ Pandey, Niraj (6 August 2008). Implementation of Leap Ahead Function for Linear Congruental and Lagged Fibonacci Generators (PDF) (MSc. thesis). Florida State University. § 2.2. Archived from the original (PDF) on 12 July 2011. Retrieved 13 April 2012.
  4. L'Ecuyer, Pierre (September–October 1996). "Combined Multiple Recursive Number Generators". Operations Research. 44 (5): 816–822. doi:10.1287/opre.44.5.816.
  5. L'Ecuyer, Pierre (January–February 1999). "Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators". Operations Research. 47 (1): 159–164. CiteSeerX 10.1.1.48.1341. doi:10.1287/opre.47.1.159.
  6. L'Ecuyer, Pierre; R. Simard; E.J. Chen; W.D. Kelton (November–December 2002). "An Object-Oriented Randon-Number Package with Many Long Streams and Substreams" (PDF). Operations Research. 50 (6): 1073–1075. CiteSeerX 10.1.1.25.22. doi:10.1287/opre.50.6.1073.358.

External links

Categories: