Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Uniform random number generation

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Math. 55(1986)455–465.

    Google Scholar 

  2. L. Afflerbach and H. Grothe, Calculation of Minkowski-reduced lattice bases, Computing 35(1985)269–276.

    Google Scholar 

  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.

    Google Scholar 

  4. L. Afflerbach and R. Weilbächer, The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers, Math. Comp. 53(1989)343–354.

    Google Scholar 

  5. D.L. André, G.L. Mullen and H. Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54(1990)737–748.

    Google Scholar 

  6. S.L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32(1990)221–251.

    Google Scholar 

  7. A.C. Atkinson, Tests of pseudo-random numbers, Appl. Statist. 29(1980)164–171.

    Google Scholar 

  8. L. Blum, M. Blum and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comp. 15(1986)364–383.

    Google Scholar 

  9. J. Boyar, Inferring sequences produced by a linear congruential generator missing low-order bits, J. Cryptol. 1(1989)177–184.

    Google Scholar 

  10. P. Bratley, B.L. Fox and L.E. Schrage,A Guide to Simulation, 2nd ed. (Springer, New York, 1987).

    Google Scholar 

  11. M. Brown and H. Solomon, On combining pseudorandom number generators, Ann. Statist. 1(1979)691–695.

    Google Scholar 

  12. B.J. Collings, Compound random number generators, J. Amer. Statist. Assoc. 82(1987)525–527.

    Google Scholar 

  13. A. Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63(1991)883–896.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  16. J. Dagpunar,Principles of Random Variate Generation (Oxford University Press, 1988).

  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.

    Google Scholar 

  19. L. Devroye,Non-Uniform Random Variate Generation (Springer, New York, 1986).

    Google Scholar 

  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).

    Google Scholar 

  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.

    Google Scholar 

  23. J. Eichenauer and J. Lehn, On the structure of quadratic congruential sequences, Manuscripta Math. 58(1987)129–140.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  26. J. Eichenauer-Herrmann, A remark on long-range correlations in multiplicative congruential pseudo random number generators, Numer. Math. 56(1989)609–611.

    Google Scholar 

  27. J. Eichenauer-Herrmann, Statistical independence of a new class of inversive congruential pseudorandom numbers, Math. Comp. 60(1993)375–384.

    Google Scholar 

  28. J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers: A tutorial, Int. Statist. Rev. 60(1992)167–176.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  34. G.S. Fishman, Multiplicative congruential random number generators with modulus 2β: An exhaustive analysis for β = 32 and a partial analysis for β = 48, Math. Comp. 54(1990)331–344.

    Google Scholar 

  35. M. Fushimi, An equivalence relation between Tausworthe and GFSR sequences and applications, Appl. Math. Lett. 2(1989)135–137.

    Google Scholar 

  36. M. Fushimi and S. Tezuka, Thek-distribution of generalized feedback shift register pseudorandom numbers, Commun. ACM 26(1983)516–523.

    Google Scholar 

  37. H. Grothe, Matrix generators for pseudo-random vector generation, Statist. Hefte 28(1987)233–238.

    Google Scholar 

  38. H. Grothe, Matrixgeneratoren zur Erzeugung gleichverteilter Pseudozufallsvektoren (in German), Dissertation (thesis), Tech. Hochschule Darmstadt, Germany (1988).

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  41. F. James, A review of pseudorandom number generators, Comp. Phys. Commun. 60(1990)329–344.

    Google Scholar 

  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.

    Google Scholar 

  43. Z.A. Karian and E.J. Dudewicz,Modern Statistical, Systems, and GPSS Simulation: The First Course (Computer Science Press, Freeman, New York, 1991).

    Google Scholar 

  44. D.E. Knuth,The Art of Computer Programming: Seminumerical Algorithms, Vol. 2, 2nd ed. (Addison-Wesley, 1981).

  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.

    Google Scholar 

  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.

    Google Scholar 

  47. A.M. Law and W.D. Kelton,Simulation Modeling and Analysis, 2nd ed. (McGraw-Hill, 1991).

  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.

    Google Scholar 

  49. P. L'Ecuyer, Random numbers for simulation, Commun. ACM 33, no. 10 (1990) 85–97.

    Google Scholar 

  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.

    Google Scholar 

  52. P. L'Ecuyer and S. Côté, Implementing a random number package with splitting facilities, ACM Trans. Math. Software 17(1991)98–111.

    Google Scholar 

  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.

    Google Scholar 

  56. A.K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comp. Syst. Sci. 30(1985)235–248.

    Google Scholar 

  57. T.G. Lewis and W.H. Payne, Generalized feedback shift register pseudorandom number algorithm, J. ACM. 20(1973)456–468.

    Google Scholar 

  58. R. Lidl and H. Niederreiter,Introduction to Finite Fields and Their Applications (Cambridge University Press, Cambridge, 1986).

    Google Scholar 

  59. J.H. Lindholm, Analysis of the pseudo-random properties of subsequences of longm-sequences, IEEE Trans. Inf. Theory IT-14(1968)569–576.

    Google Scholar 

  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.

    Google Scholar 

  62. G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Prob. 1(1991)462–480.

    Google Scholar 

  63. G. Marsaglia, B. Narasimhan and A. Zaman, A random number generator for PCs, Comp. Phys. Commun. 60(1990)345–349.

    Google Scholar 

  64. G. Marsaglia, A. Zaman and W.W. Tsang, Towards a universal random number generator, Statist. Prob. Lett. 8(1990)35–39.

    Google Scholar 

  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.

    Google Scholar 

  67. M. Matsumoto and Y. Kurita, Twisted GFSR generators II, ACM Trans. Modeling Comp. Simul., to appear.

  68. U.M. Maurer, A universal statistical test for random bit generators, J. Cryptol. 5(1992)89–105.

    Google Scholar 

  69. H. Niederreiter, Quasi-Monte Carlo methods and pseudorandom numbers, Bull. Amer. Math. Soc. 84(1978)957–1041.

    Google Scholar 

  70. H. Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46(1985)51–68.

    Google Scholar 

  71. H. Niederreiter, A pseudorandom vector generator based on finite arithmetic, Math. Japonica 31(1986)759–774.

    Google Scholar 

  72. H. Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comp. 8(1987)1035–1051.

    Google Scholar 

  73. H. Niederreiter, The serial test for digitalk-step pseudorandom numbers, Math. J. Okayama Univ. 30(1988)93–199.

    Google Scholar 

  74. H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators, J. Comp. Appl. Math. 31(1990)139–151.

    Google Scholar 

  75. H. Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31(1991)323–345.

    Google Scholar 

  76. H. Niederreiter, New methods for pseudorandom number and pseudorandom vector generation,Proc. Winter Simulation Conf. (1992) pp. 264–269.

  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).

    Google Scholar 

  78. H. Niederreiter, On a new class of pseudorandom numbers for simulation methods, J. Comp. Appl. Math., to appear.

  79. S.K. Park and K.W. Miller, Random number generators: Good ones are hard to find, Commun. ACM 31(1988)1192–1201.

    Google Scholar 

  80. W.H. Press and S.A. Teukolsky, Portable random number generators, Comp. Phys. 6(1992)522–524.

    Google Scholar 

  81. B.D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London, Series A 389(1993)197–204.

    Google Scholar 

  82. B.D. Ripley,Stochastic Simulation (Wiley, New York, 1987).

    Google Scholar 

  83. B.D. Ripley, Uses and abuses of statistical simulation, Math. Progr. 42(1988)53–68.

    Google Scholar 

  84. B.D. Ripley, Thoughts on pseudorandom number generators, J. Comp. Appl. Math. 31(1990)153–163.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  94. S. Tezuka and M. Fushimi, Calculation of Fibonacci Polynomials for GFSR sequences with low discrepancies, Math. Comp. 60(1993)763–770.

    Google Scholar 

  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.

    Google Scholar 

  96. J.P.R. Tootill, W.D. Robinson and D.J. Eagle, An asymptotically random Tausworthe sequence, J. ACM 20(1973)469–481.

    Google Scholar 

  97. D. Wang and A. Compagner, On the use of reducible polynomials as random number generators, Math. Comp. 60(1993)363–374.

    Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Département d'IRO, Université de Montréal, Succ. Centre-Ville, C.P. 6128, H3C 3J7, Montréal, Canada

    Pierre L'Ecuyer

Authors
  1. Pierre L'Ecuyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

L'Ecuyer, P. Uniform random number generation. Ann Oper Res 53, 77–120 (1994). https://doi.org/10.1007/BF02136827

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02136827

Keywords

Search

Navigation