On Parameter Selection Criteria for Linear Congruential Generators

Cyril Oseremen Odijie

doi:https://doi.org/10.59232/MS-V3I1P104

Research Article | Open Access | Download Full Text

Volume 3 | Issue 1 | Year 2025 | Article Id: MS-V3I1P104 DOI: https://doi.org/10.59232/MS-V3I1P104

On Parameter Selection Criteria for Linear Congruential Generators

Cyril Oseremen Odijie

Received	Revised	Accepted	Published
05 Jan 2025	07 Feb 2025	14 Mar 2025	31 Mar 2025

Citation

Cyril Oseremen Odijie. “On Parameter Selection Criteria for Linear Congruential Generators.” DS Journal of Modeling and Simulation, vol. 3, no. 1, pp. 45-50, 2025.

Abstract

Pseudo-Random Number Generators (PRNGs), especially Linear Congruential Generators (LCGs), have been widely studied. Their desirability lies in the ability to construct one with a long period, possibly a full period. This helps to ensure that the sequence of random integers generated satisfies desirable properties of randomness and independence to a large extent. Hull and Dobell, in 1962, had given three criteria or conditions that certain parameters of LCGs should satisfy to guarantee a full period. However, implementing the criteria has eluded many users. This short paper puts clear meanings to each condition and gives several implementable examples.

Keywords

Full-period, Hull-Dobell theorem, Linear congruential generators, Pseudorandom number generator.

References

[1] W.E. Thomson, “A Modified Congruence Method of Generating Pseudo-random Numbers,” The Computer Journal, vol. 1, no. 2, 1958.

[CrossRef] [Google Scholar] [Publisher Link]

[2] A. Rotenberg, “A New Pseudo-Random Number Generator,” Jouranl of the ACM, vol. 7, no. 1, pp. 75-77, 1960.

[CrossRef] [Google Scholar] [Publisher Link]

[3] Pierre L’Ecuyer, “Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure,” Mathematics of Computation, vol. 68, no. 225, pp. 249-260, 1999.

[CrossRef] [Google Scholar] [Publisher Link]

[4] G.L. Steele Jr., and Sebastiano Vigna, “Computationally Easy, Spectrally Good Multipliers for Congruential Pseudorandom Number Generators,” Software: Practice and Experience, vol. 52, no. 2, pp. 443-458, 2022.

[CrossRef] [Google Scholar] [Publisher Link]

[5] Pierre L'Ecuyer, “History of Uniform Random Number Generation,” Winter Simulation Conference, Las Vegas, NV, USA, 2017.

[CrossRef] [Google Scholar] [Publisher Link]

[6] T.E. Hull, and A.R. Dobell, “Random Number Generators,” SIAM Review, vol. 4, no. 3, pp. 230-254, 1962.

[CrossRef] [Google Scholar] [Publisher Link]

[7] G.S. Fishman, and L.R. More III, “An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2³¹-1,” SIAM Journal on Scientific and Statistical Computing, vol. 7, no. 1, pp. 24-45, 1986.

[CrossRef] [Google Scholar] [Publisher Link]

[8] Pierre L'Ecuyer, François Blouin, and Raymond Couture, “A Search for Good Multiple Recursive Random Number Generators”, ACM Transactions on Modeling and Computer Simulation, vol. 3, no. 2, pp. 87-98, 1993.

[CrossRef] [Google Scholar] [Publisher Link]

[9] Hui-Chin Tang, “An Analysis of Linear Congruential Random Number Generators When Multiplier Restrictions Exist,” European Journal of Operational Research, vol. 182, no. 2, pp. 820-828, 2007.

[CrossRef] [Google Scholar] [Publisher Link]

[10] S.K. Park, and K.W. Miller, “Random Number Generators: Good Ones are Hard to Find,” Communications of the ACM, vol. 31, no. 10, pp. 1192-1209, 1969.

[CrossRef] [Google Scholar] [Publisher Link]

[11] W.H. Payne, J.R. Rabung, and T.P. Bogyo, “Coding the Lehmer Pseudo-Random Number Generator,” Communications of the ACM, vol. 12, no. 2, pp. 85-86, 1969.

[CrossRef] [Google Scholar] [Publisher Link]

[12] Derrick H. Lehmer, “Mathematical Methods in Large-Scale Computing Units,” 2^nd Symposium on Large-Scale Digital Calculating Machinery, pp. 141-146, 1951.

[Google Scholar]

[13] Robert C. Tausworthe, “Random Numbers Generated by Linear Recurrence Modulo Two,” Mathematics of Computation, vol. 19, no. 90, pp. 201-209, 1965.

[CrossRef] [Google Scholar] [Publisher Link]

[14] Makoto Matsumoto, and Takuji Nishimura, “Mersenne Twister: A623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator,” ACM Transactions on Modelling and Computer Simulation, vol. 8, no. 1, pp. 3-30, 1998.

[CrossRef] [Google Scholar] [Publisher Link]

[15] George Marsaglia, “Xorshift RNGs,” Journal of Statistical Software, vol. 8, no. 14, pp. 1-6, 2003.

[CrossRef] [Google Scholar] [Publisher Link]