Extension of Linear Congruential Generator

Authors: Atif Avdović

Keywords: extension, linear congruential generator, period, modulus, randomness, number theory

Abstract:

Abstract: Random number generation is a significant research topic, even though there have already been a lot of papers published about it. Particularly detailed research has been made about the Linear Congruent Generator (LCG), which is still the most frequently used one. Research into the LCG has lead to the results in this paper in form of a new, extended LCG model. We have shown that the extended model has all the necessary features of randomness, but still a significantly larger period than the standard LCG.

References:

[1] A. AVDOVIĆ, V. JEVREMOVIĆ, Discrete Parameter-Free Zone Distribution and Its Application in Normality Testing, Axioms, Vol. 12, 12 (2023). https://doi.org/10.3390/axioms12121087 [2] A. AVDOVIĆ, V. JEVREMOVIĆ, Quantile-Zone Based Approach to Normality Testing, Mathematics, Vol. 10, 11 (2022). https://doi.org/10.3390/math10111828 [3] L. DEVROYE, Non-Uniform Random Variate Generation, Springer, New York, 1986. [4] J. EICHENAUER, H. GROTHE, J. LEHN, A. TOPUZOGLU ˘ , A multiple recursive nonlinear congruential pseudo random number generator, Manuscripta Mathematica, 59 (1987), 331–346. https://doi.org/10.1007/BF01174798 [5] G. S. FISHMAN, L. R. MOORE, An exhaustive analysis of multiplicative congruential random number generators with modulus 2 31 −1, SIAM Journal of Scientific and Statistical Computing, 7, (1986), 24-45. https://doi.org/10.1137/0907002 [6] G. S. FISHMAN, Multiplicative Congruential Random Number Generators with Modulus 2 β : An Exhaustive Analysis for β = 32 and Partial Analysis for β = 48, Mathematics of Computation, 54:189, (1990), 331-344. https://doi.org/10.1090/S0025-5718-1990-0993929-9 [7] A. T. FULLER, The Period of Pseudo-Random Numbers Generated by Lehmer’s Congruential Method, The Computer Journal, 19:2, (1976), 173–177. https://doi.org/10.1093/comjnl/19.2.173 [8] J. GENTLE, Random Number Genetarion and Monte Carlo Methods, George Mason University, Fairfax, 2002. [9] F. GOUALARD, Drawing random floating-point numbers from an interval, ACM Transactions on Modeling and Computer Simulation, 32 (3), (2022). https://hal.science/hal-03282794v4 [10] M. M. JACAK, P. JO´ ZWIAK ´ , J. NIEMCZUK, J.E. JACAK, Quantum generators of random numbers, Scientific Reports, 11:16108 (2021). https://doi.org/10.1038/s41598-021-95388-7 [11] V. JEVREMOVIĆ, A. AVDOVIĆ, Control Charts Based on Quantiles – New Approaches, Scientific Publications of the State University of Novi Pazar, Series A, Applied Mathematics, Informatics and Mechanics, Vol. 12, 2 (2020), 99-104. https://doi.org/10.5937/SPSUNP2002099J [12] V. JEVREMOVIĆ, A. AVDOVIĆ, Empirical Distribution Function as a Tool in Quality Control, Scientific Publications of the State University of Novi Pazar, Series A, Applied Mathematics, Informatics and Mechanics, Vol. 12, 1 (2020), 37-46. https://doi.org/10.5937/SPSUNP2001037J [13] D. E. KNUTH, The Art of Computer Programming. Vol. 2, Seminumerical Algorythms – Third Eddition, Addison-Wesley, Reading, Massachusetts, 1998. [14] D. H. LEHMER, Mathematical methods in large-scale computing unit, in: Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, Harvard University Press, Cambridge, Massachusetts, 1951, pp. 141–146. [15] G. MARSAGLIA, Random Number Generators, Journal of Modern Applied Statistical Methods, 2:1 (2003), 2–13. 10.22237/jmasm/1051747320 [16] V. MULDER, A. MERMOUD, V. LENDERS, B. TELLENBACH, editors, Trends in Data Protection and Encryption Technologies, Springer Nature Switzerland, Cham, Springer Science+Business Media New York, 2023. [17] S. K. PARK, K. W. MILLER, J. LEHN, Random number generators: Good ones are hard to find, Communications of the ACM, 31:10 (1988), 1192–1201. https://doi.org/10.1145/63039.63042 [18] M. SPIES, Independent topical structures identification: Theoretical approach and proof-of-concept study, Scientific Publications of the State University of Novi Pazar, Series A, Applied Mathematics, Informatics and Mechanics, Vol. 15, 1 (2023), 1-19. http://www.dunp.np.ac.rs/wp-content/uploads/2022/publikacije/serija-a/contents/vol.15no1- 2023/SP-SUNP-15-1-23-1.pdf (accessed on 13 December 2023) [19] H. C. TANG, Modulus of Linear Congruential Random Number Generator, Quality and Quantity, 39 (2005), 413-422. https://doi.org/10.1007/s11135-004-6788-6 [20] P. C. WU, Multiplicative, Congruential Random-Number Generators with Multiplier ±2 k1 ± 2 k2 and Modulus 2 p−1, ACM Transactions on Mathematical Software, 23:2 (1997), 255–265. https://doi.org/10.1145/264029.264056