Software for uniform random number generation: distinguishing the good and the bad

ABSTRACT

The requirements, design principles, and statistical testing approaches of uniform random number generators for simulation are briefly surveyed. An object-oriented random number package where random number streams can be created at will, and with convenient tools for manipulating the streams, is presented. A version of this package is now implemented in the Arena and AutoMod simulation tools. We also test some random number generators available in popular software environments such as Microsoft's Excel and Visual Basic, SUN's Java, etc., by using them on two very simple simulation problems. They fail the tests by a wide margin.

REFERENCES

• 1: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 2: Dieter, U. 1975. How to calculate shortest vectors in a lattice. Mathematics of Computation 29 (131): 827-833.
• 3: Eichenauer-Herrmann, J. 1995. Pseudorandom number generation by nonlinear methods. International Statistical Reviews 63:247-255.
• 4: Eichenauer-Herrmann, J., E. Herrmann, and S. Wegenkittl. 1997. A survey of quadratic and inversive congruential pseudorandom numbers. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, ed. P. Hellekalek, G. Larcher, H. Niederreiter, and P. Zinterhof, Volume 127 of Lecture Notes in Statistics, 66-97. New York: Springer.
• 5: Karl Entacher, Bad subsequences of well-known linear congruential pseudorandom number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.61-70, Jan. 1998 [doi>10.1145/272991.273009]
• 6: Fishman, G. S. 1996. Monte Carlo: Concepts, algorithms, and applications. Springer Series in Operations Research. New York: Springer-Verlag.
• 7: M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983 [doi>10.1145/358150.358159]
• 8: P. Hellekalek, Good random number generators are (not so) easy to find, Mathematics and Computers in Simulation, v.46 n.5-6, p.485-505, June 1998
• 9: Hellekalek, P., and G. Larcher. (Eds.) 1998. Random and quasi-random point sets, Volume 138 of Lecture Notes in Statistics. New York: Springer.
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: Lagarias, J. C. 1993. Pseudorandom numbers. Statistical Science 8 (1): 31-39.
• 12: Law, A. M., and W. D. Kelton. 1982. Confidence intervals for steady-state simulation, ii: A survey of sequential procedures. Management Science 28:550-562.
• 13: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 14: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 15: L'Ecuyer, P. 1994. Uniform random number generation. Annals of Operations Research 53:77-120.
• 16: L'Ecuyer, P. 1996a. Combined multiple recursive random number generators. Operations Research 44 (5): 816-822.
• 17: Pierre L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation, v.65 n.213, p.203-213, Jan. 1996 [doi>10.1090/S0025-5718-96-00696-5]
• 18: Pierre L'Ecuyer, Uniform random number generators, Proceedings of the 30th conference on Winter simulation, p.97-104, December 13-16, 1998, Washington, D.C., United States
• 19: Gregory W. Fischer , Ziv Carmon , Dan Ariely , Gal Zauberman , Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research, v.47 n.1, p.159-164, January 1999 [doi>10.1287/opre.47.1.159]
• 20: Pierre L'Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Mathematics of Computation, v.68 n.225, p.249-260, Jan. 1999 [doi>10.1090/S0025-5718-99-00996-5]
• 21: Pierre L'Ecuyer, Tables of maximally equidistributed combined LFSR generators, Mathematics of Computation, v.68 n.225, p.261-269, Jan. 1999 [doi>10.1090/S0025-5718-99-01039-X]
• 22: Pierre L'Ecuyer , Terry H. Andres, A random number generator based on the combination of four LCGs, Mathematics and Computers in Simulation, v.44 n.1, p.99-107, May 1997 [doi>10.1016/S0378-4754(97)00052-9]
• 23: Pierre L'Écuyer , Jean-François Cordeau , Richard Simard, Close-Point Spatial Tests and Their Application to Random Number Generators, Operations Research, v.48 n.2, p.308-317, March 2000 [doi>10.1287/opre.48.2.308.12385]
• 24: Pierre L'Ecuyer , Serge Côté, Implementing a random number package with splitting facilities, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.98-111, March 1991 [doi>10.1145/103147.103158]
• 25: L'Ecuyer, P., and R. Couture. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS Journal on Computing 9 (2): 206-217.
• 26: L'Ecuyer, P., and P. Hellekalek. 1998. Random number generators: Selection criteria and testing. In Random and Quasi-Random Point Sets, ed. P. Hellekalek and G. Larcher, Volume 138 of Lecture Notes in Statistics, 223-265. New York: Springer.
• 27: Pierre L'Ecuyer , Christiane Lemieux, Variance Reduction via Lattice Rules, Management Science, v.46 n.9, p.1214-1235, September 2000 [doi>10.1287/mnsc.46.9.1214.12231]
• 28: Pierre L'Ecuyer , Francois Panneton, A new class of linear feedback shift register generators, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 29: Pierre L'Ecuyer , Richard Simard, Beware of linear congruential generators with multipliers of the form a = ±2q ±2r, ACM Transactions on Mathematical Software (TOMS), v.25 n.3, p.367-374, Sept. 1999 [doi>10.1145/326147.326156]
• 30: Pierre L'Ecuyer , Richard Simard, On the performance of birthday spacings tests with certain families of random number generators, Mathematics and Computers in Simulation, v.55 n.1-3, p.131-137, Feb. 15, 2001 [doi>10.1016/S0378-4754(00)00253-6]
• 31: L'Ecuyer, P., R. Simard, E. J. Chen, and W. D. Kelton. 2001. An object-oriented random-number package with many long streams and substreams. Submitted.
• 32: Pierre L'Ecuyer , Richard Simard , Stefan Wegenkittl, Sparse Serial Tests of Uniformity for Random Number Generators, SIAM Journal on Scientific Computing, v.24 n.2, p.652-668, 2002 [doi>10.1137/S1064827598349033]
• 33: Pierre L'Ecuyer , Renée Touzin, Fast combined multiple recursive generators with multipliers of the form a = ±2^q ±2^r, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 34: Lewis, P. A. W., A. S. Goodman, and J. M. Miller. 1969. A pseudo-random number generator for the system/360. IBM System' s Journal 8:136-143.
• 35: Marsaglia, G. 1985. A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface, 3-10. North-Holland, Amsterdam: Elsevier Science Publishers.
• 36: Michael Mascagni , Ashok Srinivasan, Algorithm 806: SPRNG: a scalable library for pseudorandom number generation, ACM Transactions on Mathematical Software (TOMS), v.26 n.3, p.436-461, Sept. 2000 [doi>10.1145/358407.358427]
• 37: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators II, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.254-266, July 1994 [doi>10.1145/189443.189445]
• 38: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 39: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 40: Takuji Nishimura, Tables of 64-bit Mersenne twisters, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.4, p.348-357, Oct. 2000 [doi>10.1145/369534.369540]
• 41: Art B. Owen, Latin supercube sampling for very high-dimensional simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.71-102, Jan. 1998 [doi>10.1145/272991.273010]
• 42: Soto, J. 1999. Statistical testing of random number generators. Available at http://csrc.nist.gov/rng/rng5.html.
• 43: Tausworthe, R. C. 1965. Random numbers generated by linear recurrence modulo two. Mathematics of Computation 19:201-209.
• 44: Tezuka, S. 1995. Uniform random numbers: Theory and practice. Norwell, Mass.: Kluwer Academic Publishers.
• 45: J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical software
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

General Terms:
Algorithms, Design, Performance