请输入您要查询的百科知识：

　

词条 Combined linear congruential generator
释义

  1. Derivation

  2. Properties

  3. Example

  4. See also

  5. References

  6. External links

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

The algorithm is defined as:[3]

where:

is the "modulus" of the first LCG

is the ith input from the jth LCG

is the ith generated random integer

with:

where 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:[4]

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

Properties

The CLCG provides an efficient way to calculate pseudo-random numbers. The LCG algorithm is computationally inexpensive to use.[7] 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.[8]

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

Example

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

LCGs are used with the following properties:

The CLCG algorithm is set up as follows:

1. The seed for the first LCG, , should be selected in the range of [1, 2147483562].

The seed for the second LCG, , should be selected in the range of [1, 2147483398].

Set:

2. The two LCGs are evaluated as follows:

3. The CLCG equation is solved as shown below:

4. Calculate the random number:

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:.[11]

This equates to 2.1×109 for the two LCGs used.

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

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:.[12] Other algorithms using the CLCG method have been used to create pseudo-random number generators with periods as long as 3x1057.[13][14][15]

See also

  • Linear congruential generator

References

1. ^Banks 2010, Sec. 7.3.2
2. ^Banks 2010, Sec. 7.3.2
3. ^L'Ecuyer 1988
4. ^L'Ecuyer 1988
5. ^L'Ecuyer 1988
6. ^Banks 2010, Sec. 7.3.2
7. ^Pandey 2008, Sec. 2.2
8. ^Pandey 2008, Sec. 2.2
9. ^Banks 2010, Sec. 7.3.2
10. ^L'Ecuyer 1988
11. ^Banks 2010, Sec. 7.3.2
12. ^Banks 2010, Sec. 7.3.2
13. ^L'Ecuyer 1996
14. ^L'Ecuyer 1999
15. ^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}}.

  • {{cite journal | author = P. L'Ecuyer |title=Efficient and Portable Combined Random Number Generators |journal=Communications of the ACM |year=1988 |volume=31 |issue=6 |pages=742–749, 774 |doi=10.1145/62959.62969}}
  • {{cite journal | author = P. L'Ecuyer |title=Combined Multiple Recursive Number Generators|journal=Operations Research |year=1996 |volume=44 |issue=5|pages=816–822 |doi=10.1287/opre.44.5.816}}
  • {{cite journal | author = P. L'Ecuyer |title=Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators|journal=Operations Research |year=1999 |volume=47 |pages=159–164 |doi=10.1287/opre.47.1.159}}
  • {{cite journal |author1=P. L'Ecuyer |author2=R. Simard |author3=E.J. Chen |author4=W.D. Kelton |title=An Object-Oriented Randon-Number Package with Many Long Streams and Substreams|journal=Operations Research |year=2002 |volume=50 |issue=6 |pages=1073–1075 |doi=10.1287/opre.50.6.1073.358|citeseerx=10.1.1.25.22 }}

External links

  • [https://www.msu.edu/~amthoral/random.ppt An overview of use and testing of pseudo-random number generators ]
{{DEFAULTSORT:Combined Linear Congruential Generator}}

2 : Pseudorandom number generators|Modular arithmetic
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/22 20:29:05