Uniform random number generation.(English)Zbl 0843.65004

This article provides a survey of pseudorandom number generators (i.e., deterministic recursive formulas from $$\{1, 2,\dots,m\}$$ to $$\{1, 2,\dots,m\}$$ for a given large prime number $$m$$) that attempt to produce a sequence (here, $$k/m$$) which approximates a sequence of truly independent random variables uniformly distributed over the interval $$[0, 1]$$. Aside from necessary definitions and descriptions of most commonly used generators, the center of attention is paid to discussing criteria for a good generator such as: statistical properties (testing the generator versus known laws of probability), long period (in demand for massive simulations in physics and chemistry), speed and low memory requirement (to make the generator practical for currently available computers).
A word of caution is given to an inexperienced user about a host of packages known to offer notoriously bad generators. The author tested 9 generators versus 10 standard tests (including the poker test, the runs-up test, the birthday spacing test) and recommends the multiple recursive generator (MRG): $$x_n= (a_1 x_{n- 1}+\cdots+ a_k x_{n- k})\text{ mod }m$$ with $$m= 2^{31}- 1$$, $$k= 5$$, $$a_1= 107374182$$, $$a_5= 104480$$, $$a_2= a_3= a_4= 0$$. An extensive bibliography makes this survey a good source for both novice and a specialist. It would be of interest to learn about good generators with long period $$m$$ of order $$\sim 10^p$$, $$p\geq 100$$.

MSC:

 65C10 Random number generation in numerical analysis 11K45 Pseudo-random numbers; Monte Carlo methods

Software:

PSEUDORAN; AS 183; ACARRYPC
Full Text:

References:

 [1] L. Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Math. 55(1986)455–465. · Zbl 0601.65005 [2] L. Afflerbach and H. Grothe, Calculation of Minkowski-reduced lattice bases, Computing 35(1985)269–276. · Zbl 0557.10025 [3] L. Afflerbach and H. Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, J. Comp. Appl. Math. 23(1988)127–131. · Zbl 0658.65006 [4] L. Afflerbach and R. Weilbächer, The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers, Math. Comp. 53(1989)343–354. · Zbl 0672.65008 [5] D.L. André, G.L. Mullen and H. Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54(1990)737–748. · Zbl 0699.65003 [6] S.L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32(1990)221–251. · Zbl 0708.65004 [7] A.C. Atkinson, Tests of pseudo-random numbers, Appl. Statist. 29(1980)164–171. · Zbl 0441.65005 [8] L. Blum, M. Blum and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comp. 15(1986)364–383. · Zbl 0602.65002 [9] J. Boyar, Inferring sequences produced by a linear congruential generator missing low-order bits, J. Cryptol. 1(1989)177–184. · Zbl 0673.94009 [10] P. Bratley, B.L. Fox and L.E. Schrage,A Guide to Simulation, 2nd ed. (Springer, New York, 1987). · Zbl 0515.68070 [11] M. Brown and H. Solomon, On combining pseudorandom number generators, Ann. Statist. 1(1979)691–695. · Zbl 0404.65005 [12] B.J. Collings, Compound random number generators, J. Amer. Statist. Assoc. 82(1987)525–527. · Zbl 0641.65006 [13] A. Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63(1991)883–896. [14] R. Couture, P. L’Ecuyer and S. Tezuka, On the distribution ofk-dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60(1993)511–516 and 749–761. [15] R. Couture and P. L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. 62(1994)798–808. · Zbl 0803.65005 [16] J. Dagpunar,Principles of Random Variate Generation (Oxford University Press, 1988). · Zbl 0676.62002 [17] J.W. Dalle Molle, M.J. Hinich and D.J. Morrice, Higher-order cumulant spectral based statistical tests of pseudo random variate generators,Proc. Winter Simulation Conf. (1992) pp. 618–625. [18] A. De Matteis and S. Pagnutti, Parellelization of random number generators and long-range correlations, Numer. Math. 53(1988)595–608. · Zbl 0633.65006 [19] L. Devroye,Non-Uniform Random Variate Generation (Springer, New York, 1986). · Zbl 0593.65005 [20] E.J. Dudewicz and T.G. Ralley,The Handbook of Random Number Generation and Testing with TESTRAND Computer Code (American Sciences Press, Columbus, Ohio, 1981). · Zbl 0478.65003 [21] M.J. Durst, Using linear congruential generators for parallel random number generation,Proc. Winter Simulation Conf. (1989) pp. 462–466. [22] J. Eichenauer and J. Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27(1986)315–326. · Zbl 0607.65001 [23] J. Eichenauer and J. Lehn, On the structure of quadratic congruential sequences, Manuscripta Math. 58(1987)129–140. · Zbl 0598.65004 [24] J. Eichenauer, H. Grothe, J. Lehn and A. Topuzoğlu, A multiple recursive nonlinear congruential pseudorandom number generator, Manuscripta Math. 59(1987)331–346. · Zbl 0609.65005 [25] J. Eichenauer, J. Lehn and A. Topuzoğlu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51(1988)757–759. · Zbl 0701.65008 [26] J. Eichenauer-Herrmann, A remark on long-range correlations in multiplicative congruential pseudo random number generators, Numer. Math. 56(1989)609–611. · Zbl 0662.65003 [27] J. Eichenauer-Herrmann, Statistical independence of a new class of inversive congruential pseudorandom numbers, Math. Comp. 60(1993)375–384. · Zbl 0795.65002 [28] J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers: A tutorial, Int. Statist. Rev. 60(1992)167–176. · Zbl 0766.65002 [29] J. Eichenauer-Herrmann and H. Grothe, A new inversive congruential pseudorandom number generator with power of two modulus, ACM Trans. Modeling Comp. Simul. 2(1992)1–11. · Zbl 0844.11051 [30] J. Eichenauer-Herrmann, H. Grothe and J. Lehn, On the period length of pseudorandom vector sequences generated by matrix generators, Math. Comp. 52(1989)145–148. · Zbl 0657.65008 [31] E.D. Erdmann, Empirical tests of binary keystreams, Master’s Thesis, Department of Mathematics, Royal Holloway and Bedford New College, University of London (1992). [32] A.M. Ferrenberg, D.P. Landau and Y.J. Wong, Monte Carlo simulations: Hidden errors from ”good” random number generators, Phys. Rev. Lett. 69(1992)3382–3384. [33] G.S. Fishman and L.S. Moore III, An exhaustive analysis of multiplicative congruential random number generators with modulus 231 - 1, SIAM J. Statist. Comp. 7(1986)24–45. · Zbl 0603.65003 [34] G.S. Fishman, Multiplicative congruential random number generators with modulus 2{$$\beta$$}: An exhaustive analysis for {$$\beta$$} = 32 and a partial analysis for {$$\beta$$} = 48, Math. Comp. 54(1990)331–344. · Zbl 0686.65004 [35] M. Fushimi, An equivalence relation between Tausworthe and GFSR sequences and applications, Appl. Math. Lett. 2(1989)135–137. · Zbl 0707.94007 [36] M. Fushimi and S. Tezuka, Thek-distribution of generalized feedback shift register pseudorandom numbers, Commun. ACM 26(1983)516–523. · Zbl 0515.68047 [37] H. Grothe, Matrix generators for pseudo-random vector generation, Statist. Hefte 28(1987)233–238. · Zbl 0629.65006 [38] H. Grothe, Matrixgeneratoren zur Erzeugung gleichverteilter Pseudozufallsvektoren (in German), Dissertation (thesis), Tech. Hochschule Darmstadt, Germany (1988). · Zbl 0652.65008 [39] J.R. Heringa, H.W.J. Blöte and A. Compagner, New primitive trinomials of Mersenne-exponent degrees for random-number generation, Int. J. Mod. Phys. C3(1992)561–564. · Zbl 0940.11506 [40] D.C. Hoaglin and M.L. King, A remark on algorithm AS 98: The spectral test for the evaluation of congruential pseudo-random generators, Appl. Statist. 27(1978)375–377. [41] F. James, A review of pseudorandom number generators, Comp. Phys. Commun. 60(1990)329–344. · Zbl 0875.65021 [42] R. Kannan, A.K. Lenstra and L. Lovász, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comp. 50(1988)235–250. · Zbl 0654.12001 [43] Z.A. Karian and E.J. Dudewicz,Modern Statistical, Systems, and GPSS Simulation: The First Course (Computer Science Press, Freeman, New York, 1991). · Zbl 0754.65004 [44] D.E. Knuth,The Art of Computer Programming: Seminumerical Algorithms, Vol. 2, 2nd ed. (Addison-Wesley, 1981). · Zbl 0477.65002 [45] H. Krawczyk, How to predict congruential generators, in: Lecture Notes in Computer Science 435,Advances in Cryptology: Proceedings of Crypto ’89, ed. G. Brassard (Springer, Berlin, 1989) pp. 138–153. [46] Y. Kurita and M. Matsumoto, Primitivet-nomials (t = 3,5) overGF(2) whose degree is a Mersenne exponent 44497, Math. Comp. 56(1991)817–821. · Zbl 0717.11003 [47] A.M. Law and W.D. Kelton,Simulation Modeling and Analysis, 2nd ed. (McGraw-Hill, 1991). · Zbl 0489.65007 [48] P. L’Ecuyer, Efficient and portable combined random number generators, Commun. ACM 31(1988)742–749 and 774. See also the correspondence in the same journal, 32(1989)1019–1024. [49] P. L’Ecuyer, Random numbers for simulation, Commun. ACM 33, no. 10 (1990) 85–97. [50] P. L’Ecuyer, Testing random number generators,Proc. Winter Simulation Conf. (1992) pp. 305–313. [51] P. L’Ecuyer, F. Blouin and R. Couture, A search for good multiple recursive random number generators, ACM Trans. Modeling Comp. Simul. 3(1993)87–98. · Zbl 0842.65004 [52] P. L’Ecuyer and S. Côté, Implementing a random number package with splitting facilities, ACM Trans. Math. Software 17(1991)98–111. · Zbl 0900.65008 [53] P. L’Ecuyer and R. Couture, An implementation of the lattice and spectral tests for linear congruential and multiple recursive generators, submitted. [54] P. L’Ecuyer and R. Proulx, About polynomial-time ”unpredictable” generators,Proc. Winter Simulation Conf. (1989) pp. 467–476. [55] P. L’Ecuyer and S. Tezuka, Structural properties for two classes of combined random number generators, Math. Comp. 57(1991)735–746. · Zbl 0748.65007 [56] A.K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comp. Syst. Sci. 30(1985)235–248. · Zbl 0577.12013 [57] T.G. Lewis and W.H. Payne, Generalized feedback shift register pseudorandom number algorithm, J. ACM. 20(1973)456–468. · Zbl 0266.65009 [58] R. Lidl and H. Niederreiter,Introduction to Finite Fields and Their Applications (Cambridge University Press, Cambridge, 1986). · Zbl 0629.12016 [59] J.H. Lindholm, Analysis of the pseudo-random properties of subsequences of longm-sequences, IEEE Trans. Inf. Theory IT-14(1968)569–576. [60] G. Marsaglia, A current view of random number generation, in:Computer Science and Statistics, Proc. 16th Symp. on the Interface (Elsevier Science/North-Holland, 1985) pp. 3–10. [61] G. Marsaglia and L.-H. Tsay, Matrices and the structure of random number sequences, Lin. Alg. Appl. 67(1985)147–156. · Zbl 0572.65002 [62] G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Prob. 1(1991)462–480. · Zbl 0733.65005 [63] G. Marsaglia, B. Narasimhan and A. Zaman, A random number generator for PCs, Comp. Phys. Commun. 60(1990)345–349. · Zbl 0997.65510 [64] G. Marsaglia, A. Zaman and W.W. Tsang, Towards a universal random number generator, Statist. Prob. Lett. 8(1990)35–39. · Zbl 0692.65001 [65] M. Matsumoto and Y. Kurita, The fixed point of anm-sequence and local non-randomness, Technical Report 88-027, Department of Information Science, University of Tokyo (1988). [66] M. Matsumoto and Y. Kurita, Twisted GFSR generators, ACM Trans. Modeling Comp. Simul. 2(1992)179–194. · Zbl 0849.94014 [67] M. Matsumoto and Y. Kurita, Twisted GFSR generators II, ACM Trans. Modeling Comp. Simul., to appear. · Zbl 0849.94015 [68] U.M. Maurer, A universal statistical test for random bit generators, J. Cryptol. 5(1992)89–105. · Zbl 0790.94014 [69] H. Niederreiter, Quasi-Monte Carlo methods and pseudorandom numbers, Bull. Amer. Math. Soc. 84(1978)957–1041. · Zbl 0404.65003 [70] H. Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46(1985)51–68. · Zbl 0554.65006 [71] H. Niederreiter, A pseudorandom vector generator based on finite arithmetic, Math. Japonica 31(1986)759–774. · Zbl 0619.65002 [72] H. Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comp. 8(1987)1035–1051. · Zbl 0634.65003 [73] H. Niederreiter, The serial test for digitalk-step pseudorandom numbers, Math. J. Okayama Univ. 30(1988)93–199. [74] H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators, J. Comp. Appl. Math. 31(1990)139–151. · Zbl 0708.65007 [75] H. Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31(1991)323–345. · Zbl 0737.65001 [76] H. Niederreiter, New methods for pseudorandom number and pseudorandom vector generation,Proc. Winter Simulation Conf. (1992) pp. 264–269. · Zbl 0849.11055 [77] H. Niederreiter,Random Number Generation and Quasi-Monte Carlo Methods, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63 (SIAM, Philadelphia, 1992). · Zbl 0761.65002 [78] H. Niederreiter, On a new class of pseudorandom numbers for simulation methods, J. Comp. Appl. Math., to appear. · Zbl 0823.65010 [79] S.K. Park and K.W. Miller, Random number generators: Good ones are hard to find, Commun. ACM 31(1988)1192–1201. [80] W.H. Press and S.A. Teukolsky, Portable random number generators, Comp. Phys. 6(1992)522–524. [81] B.D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London, Series A 389(1993)197–204. · Zbl 0516.65003 [82] B.D. Ripley,Stochastic Simulation (Wiley, New York, 1987). · Zbl 0613.65006 [83] B.D. Ripley, Uses and abuses of statistical simulation, Math. Progr. 42(1988)53–68. · Zbl 0646.65003 [84] B.D. Ripley, Thoughts on pseudorandom number generators, J. Comp. Appl. Math. 31(1990)153–163. · Zbl 0701.65006 [85] A.W. Schrift and A. Shamir, The discrete log is very discreet,Proc. STOC ’90 (ACM Publ., 1990) pp. 405–415. [86] Y.S. Sherif and R.G. Dear, Development of a new composite pseudo-random number generator, Microelectronics and Reliability 30(1990)545–553. [87] M.S. Stephens, Tests for the uniform distribution, in:Goodness-of-Fit Techniques, eds. R.B. D’Agostino and M.S. Stephens (Marcel Dekker, 1986) pp. 331–366. [88] R.C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19(1965)201–209. · Zbl 0137.34804 [89] S. Tezuka, Lattice structure of pseudorandom sequences from shift-register generators,Proc. Winter Simulation Conf. (1990) pp. 266–269. [90] S. Tezuka, A unified view of long-period random number generators, submitted for publication (1992). [91] S. Tesuka and P. L’Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Trans. Modeling Comp. Simul. 1(1991)99–112. · Zbl 0844.65003 [92] S. Tezuka and P. L’Ecuyer, Analysis of add-with-carry and subtract-with-borrow generators,Proc. Winter Simulation Conf. (1992) pp. 443–447. [93] S. Tezuka, P. L’Ecuyer and R. Couture, On the add-with-carry and subtract-with-borrow random number generators, ACM Trans. Modeling Comp. Simul. 3(1994)315–331. · Zbl 0843.65003 [94] S. Tezuka and M. Fushimi, Calculation of Fibonacci Polynomials for GFSR sequences with low discrepancies, Math. Comp. 60(1993)763–770. · Zbl 0777.65002 [95] J.P.R. Tootill, W.D. Robinson and A.G. Adams, The runs up-and-down performance of Tausworthe pseudo-random number generators, J. ACM 18(1971)381–399. · Zbl 0225.65012 [96] J.P.R. Tootill, W.D. Robinson and D.J. Eagle, An asymptotically random Tausworthe sequence, J. ACM 20(1973)469–481. · Zbl 0266.65008 [97] D. Wang and A. Compagner, On the use of reducible polynomials as random number generators, Math. Comp. 60(1993)363–374. · Zbl 0795.65001 [98] B.A. Wichmann and I.D. Hill, An efficient and portable pseudo-random number generator, Appl. Statist. 31(1982)188–190. See also corrections and remarks in the same journal by Wichmann and Hill, 33(1984)123; McLeod, 34(1985)198–200; Zeisel, 35(1986)89.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.