Random numbers for simulation

ABSTRACT

In the mind of the average computer user, the problem of generating uniform variates by computer has been solved long ago. After all, every computer :system offers one or more function(s) to do so. Many software products, like compilers, spreadsheets, statistical or numerical packages, etc. also offer their own. These functions supposedly return numbers that could be used, for all practical purposes, as if they were the values taken by independent random variables, with a uniform distribution between 0 and 1. Many people use them with faith and feel happy with the results. So, why bother? Other (less naive) people do not feel happy with the results and with good reasons. Despite renewed crusades, blatantly bad generators still abound, especially on microcomputers [55, 69, 85, 90, 100]. Other generators widely used on medium-sized computers are perhaps not so spectacularly bad, but still fail some theoretical and/or empirical statistical tests, and/or generate easily detectable regular patterns [56, 65]. Fortunately, many applications appear quite robust to these defects. But with the rapid increase in desktop computing power, increasingly sophisticated simulation studies are being performed that require more and more “random” numbers and whose results are more sensitive to the quality of the underlying generator [28, 40, 65, 90]. Sometimes, using a not-so-good generator can give totally misleading results. Perhaps this happens rarely, but can be disastrous in some cases. For that reason, researchers are still actively investigating ways of building generators. The main goal is to design more robust generators without having to pay too much in terms of portability, flexibility, and efficiency. In the following sections, we give a quick overview of the ongoing research. We focus mainly on efficient and recently proposed techniques for generating uniform pseudorandom numbers. Stochastic simulations typically transform such numbers to generate variates according to more complex distributions [13, 25]. Here, “uniform pseudorandom” means that the numbers behave from the outside as if they were the values of i.i.d. random variables, uniformly distributed over some finite set of symbols. This set of symbols is often a set of integers of the form {0, . . . , m - 1} and the symbols are usually transformed by some function into values between 0 and 1, to approximate the U(0, 1) distribution. Other tutorial-like references on uniform variate generation include [13, 23, 52, 54, 65, 84, 89].

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Afflerbach, L. The sub-lattice structure of linear congruential random number generators. Manzcsc. Math. 55 (1986), 455-465.
	2	L. Afflerbach , H. Grothe, Calculation of Minkowski-reduced lattice bases, Computing, v.35 n.3-4, p.269-276, 1985 [doi>10.1007/BF02240194]
	3	L. Afflerbach , H. Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, Journal of Computational and Applied Mathematics, v.23 n.1, p.127-131, July 1988 [doi>10.1016/0377-0427(88)90338-X]
	4	Afflerbach, L. and Weilbacher, R. On Using Discrepancy for the Assessment of Pseudorandom Num-ber Generators. Submitted for publication, 1988.
	5	Afflerbach, L. and Weilbacher, R. The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers. Math. of Comput. 53, 187 (July 1989) 343-354.
	6	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	7	Andre, D. L., Mullen, G. L., and Niederreiter, H. Figures of merit for digital multistep pseudorandom numbers. Math. of Comput. To be published, 1990.
	8	A. C. Arvillias , D. G. Maritsas, Partitioning the Period of a Class of m-Sequences and Application to Pseudorandom Number Generation, Journal of the ACM (JACM), v.25 n.4, p.675-686, Oct. 1978 [doi>10.1145/322092.322106]
	9	L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
	10	Joan Boyar, Inferring sequences produced by pseudo-random number generators, Journal of the ACM (JACM), v.36 n.1, p.129-141, Jan. 1989 [doi>10.1145/58562.59305]
	11	Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	12	Paul Bratley , Bennett L. Fox, ALGORITHM 659: implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.88-100, March 1988 [doi>10.1145/42288.214372]
	13	Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	14	Brown, M. and Solomon, H. On combining pseudorandom number generators. Ann. Stat. I (1979) 691-695.
	15	David F. Carta, Two fast implementations of the “minimal standard” random number generator, Communications of the ACM, v.33 n.1, p.87-88, Jan. 1990 [doi>10.1145/76372.76379]
	16	William Celmaster , K J M Moriarty, A method for vectorized random number generators, Journal of Computational Physics, v.64 n.1, p.271-275, May 1986 [doi>10.1016/0021-9991(86)90032-X]
	17	Chassaing, P. An optimal random number generator on Z,. Stat. and Prob. Lett. 7 (1989) 307-309.
	18	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	19	Chung, F. R. K., Diaconis, P., and Graham, R. L. Random walks arising in random number generation. Ann. Probab. 15, 3 (1987) 1148-1165.
	20	Collings, B. J. Compound random number generators. J. Am. Stat. Assoc. 82, 398 (1987) 525-527.
	21	Bruce Jay Collings , G. Barry Hembree, Initializing generalized feedback shift register pseudorandom number generators, Journal of the ACM (JACM), v.33 n.4, p.706-711, Oct. 1986 [doi>10.1145/6490.6493]
	22	A. Compagner , A. Hoogland, Maximum-length sequences, cellular automata, and random numbers, Journal of Computational Physics, v.71 n.2, p.391-428, August 1, 1987 [doi>10.1016/0021-9991(87)90037-4]
	23	Dagpunar, J. Principles of Random Variate Generation. Oxford University Press, 1988.
	24	A. De Matteis , S. Pagnutti, Parallelization of random number generators and long-range correlations, Numerische Mathematik, v.53 n.5, p.595-608, August 1988 [doi>10.1007/BF01397554]
	25	Devroye, L. Non-Uniform Random Variate Generation. Springer- Verlag, New York, 1986.
	26	Dieter, U. How to calculate shortest vectors in a lattice. Math. Comput., 29, 131 (1975) 827-833.
	27	Dudewicz, E. J. and Ralley, T. G. The Handbook of Random Number Generation and Testing with TESTRAND Computer Code. American Sciences Press, Columbus, Ohio, 1981.
	28	M. J. Durst, Using linear congruential generators for parallel random number generation, Proceedings of the 21st conference on Winter simulation, p.462-466, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76798]
	29	Eichenauer, J. and Lehn, J. A Nonlinear congruential pseudorandom number generator. Statist&he Hefie, 27 (1986) 3 15- 326.
	30	Eichenauer, J. and Lehn, J. On the structure of quadratic congruential sequences. Manux. Math., 58 (1987) 129-140.
	31	Eichenauer. J., Grothe, H., Lehn. J. and Topuzoglu, A. A multiple recursive nonlinear congruential pseudorandom number generator. Manw. Math. 59 (I 987) 33 I - 346.
	32	Eichenauer, J., Lehn, J. and Topuzoglu, A. .4 nonlinear congruential pseudorandom number generator with power of two modulus. Math. Comput. 51, 184 (1988) 757-759.
	33	Eichenauer-Herrmann, J., Grothe, H. and Lehn, J. On the period length of pseudorandom vector sequences generated by matrix generators. Math. Comput. 52, 185 (1989) 145-148.
	34	Eichenauer-Herrmann, J. lnversive congruential pseudorandom numbers avoid the planes. Math. Comput. (I 990). To be published.
	35	Fishman, G. S. Multiplicative congruential random number generators with modulus 2P: an exhaustive analysis for /3 = 32 and a partial analysis for /3 = 48. Math. Comput. 54, 189 (Jan 1990) 331- 344.
	36	George A Fishman , Louis R Moore, III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.24-45, Jan. 1986 [doi>10.1137/0907002]
	37	Fushimi, M. Increasing the orders of equidistribution of the leading bits of the Tausworthe sequence. InJ hoc. Lett. 16 (1983) 189-192.
	38	Masanori Fushimi, Designing a uniform random number generator whose subsequences are k-distributed, SIAM Journal on Computing, v.17 n.1, p.89-99, Feb. 1988 [doi>10.1137/0217006]
	39	Fushimi, M. An equivalence relation between Tausworthe and GFSR sequences and applications. Applied Math. Lett. :?, 2 (I 989) 135- 137.
	40	M. Fushimi, Random number generation on parallel processors, Proceedings of the 21st conference on Winter simulation, p.459-461, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76797]
	41	Fushimi, M. Random number generation with the recursion X, = X,-jp @ X,--3y. In Comput. and Applied Math. (1990). To be published.
	42	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]
	43	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	44	Grothe, H. Matrix generators for pseudo-random vectors generation. Stat. Hefte 28 (I 987) 233-238.
	45	Grothe, H. Matrixgeneratoren zur Erzeugung gleichverteilter Pseudozufallsvektoren (in german). Dissertation (thesis), Tech. Hochschule Darmstadt, Germany, 1988.
	46	Grube, A. Mehrfach rekursiverzeugte Pseudo-Zufallszahlen (in german). Zeitschrift fiir angewandte Math. und Mechanik 53 (1973) T223-T225.
	47	D. Guinier, A fast uniform astronomical random number generator, ACM SIGSAC Review, v.7 n.1, p.1-12, Spring 1989 [doi>10.1145/70951.70952]
	48	Alexander Haas, The multiple prime random number generator, ACM Transactions on Mathematical Software (TOMS), v.13 n.4, p.368-381, Dec. 1987 [doi>10.1145/35078.214349]
	49	J. H. Halton, Pseudo-random trees: multiple independent sequence generators for parallel and branching computations, Journal of Computational Physics, v.84 n.1, p.1-56, Sep. 1989 [doi>10.1016/0021-9991(89)90180-0]
	50	John M Hosack, The use of Cebysev mixing to generate pseudo-random numbers, Journal of Computational Physics, v.67 n.2, p.482-486, Dec. 1986 [doi>10.1016/0021-9991(86)90274-3]
	51	Kannan, R., Lenstra, A. K. and Lov&sz, L. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math. Comput. 50, 181 (1988) 235-250.
	52	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	53	A. E. Koniges , C. E. Leith, Parallel processing of random number generation for Monte Carlo turbulence simulation, Journal of Computational Physics, v.81 n.1, p.230-235, March 1989 [doi>10.1016/0021-9991(89)90072-7]
	54	Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
	55	L'Ecuyer, P. A portable random number generat.or for 16.bit computers. Modelzng and Simulation on Microcomputers 1987. The Society for Computer Simulation (1987), pp. 45-49.
	56	P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
	57	Pierre L'Ecuer , François Blouin, Linear congruential generators of order K>1, Proceedings of the 20th conference on Winter simulation, p.432-439, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318229]
	58	L'Ecuyer, P. and Blouin, F. Multiple Recursive and Matrix Linear Congruential Generators. Submitted for publication, 1990.
	59	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]
	60	P. L'Ecuyer , R. Proulx, About polynomial-time “unpredictable” generators, Proceedings of the 21st conference on Winter simulation, p.467-476, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76799]
	61	L'Ecuyer, P. and Tezuka, S. Structural Properties for Two Classes of Combined Generators. Submitted for publication, 1990.
	62	T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
	63	Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
	64	Marsaglia, G. Random numbers fall mainly in the planes. In Proceedings of the National Academy of Sciences of the United States of America 60 (1968) pp. 25-28.
	65	Marsaglia, G. A Current View of Random Number Generation. Computer science and statistics. In Proceedings of the Sixteenth Symposium on the Interface (Atlanta, March 1984). Elsevier Science Pub}., North-Holland, 1985, pp. 3-10.
	66	Marsaglia, G. and Tsay, L.-H. Matrices and the structure of random number sequences. Linear Algebra and its Appl. 67 (1985) 147- 156.
	67	Marsaglia, G., Zaman, A., and Tsang, W. W. Towards a universal random number generator. Stat. and Prob. Lett. 8 (1990) 35-39.
	68	Marse, K. and Roberts, S. D. lmplementing a portable FORTRAN uniform (0,l) generator. Simulation 41, 4 (1983) 135-139.
	69	Doan T. Modianos , Robert C. Scott , Larry W. Cornwell, Testing intrinsic random-number generators, BYTE, v.12 n.1, p.175-178, Jan. 1987
	70	Monahan, J. F. Accuracy in Random Number Generation. Math. of Corn& 45, 172 (1985) 559-568.
	71	Morain, F. lmplementation of the Atkin-Goldwasser-Kilian primality testing algorithm. Rap. de recherthe 9 11, INRIA, Rocquencourt, France, 1988.
	72	G. L. Mullen , H. Niederreiter, Optimal characteristic polynomials for digital multistep Pseudorandom numbers, Computing, v.39 n.2, p.155-163, April 1, 1987 [doi>10.1007/BF02310104]
	73	Nance, R. E. and Overstreet, C., Jr. Some experimental observations on the behavior of composite random number generators. Oper. Res. 26, 5 (1978) 915-935.
	74	Narkiewicz, W. CJninz~orm Distribution of Sequences of Integers in Residue Classes. Lecture Notes in Mathematics, 1087, Springer-Verlag, 1984.
	75	Niederreiter, H. Quasi-Monte Carlo methods and pseudorandom numbers. Bull. Am. Math. Sot. 84, 6 (1978) 957-1041.
	76	Niederreiter, H. A pseudorandom vector generator based on finite field arithmetic. Math. Japonica 31, 5 (1986) 759-774.
	77	Harald Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1035-1051, November 1, 1987 [doi>10.1137/0908084]
	78	Niederreiter, H. Remarks on nonlinear congruential pseudorandom numbers. Metriha 35 (1988) 321-328.
	79	Niederreiter, H. Statistical independence of nonlinear congruential pseudorandom numbers. Monatshefte fiir Mathematik 106 (1988) 149- 159.
	80	Niederreiter, H. The Serial Test for Digital k-Step Pseudorandom Numbers. Math. J. Okayama Univ. 30 (1988) 93-l 19.
	81	Niederreiter, H. The serial test for congruential pseudorandom numbers generated by inversions. Math. of Comput. 52, 185 (1989) 135-144.
	82	Niederreiter, H. Lower bounds for the discrepancy of inversive congruential pseudorandom numbers. Math. Comput. 1990. To be published.
	83	H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators, Journal of Computational and Applied Mathematics, v.31 n.1, p.139-151, July 1990 [doi>10.1016/0377-0427(90)90345-Z]
	84	Harald Niederreiter, Recent trends in random number and random vector generation, Annals of Operations Research, v.31 n.1-4, p.323-346, June 1991 [doi>10.1007/BF02204856]
	85	S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
	86	Ora E. Percus , Malvin H. Kalos, Random number generators for MIMD parallel processors, Journal of Parallel and Distributed Computing, v.6 n.3, p.477-497, June 1989 [doi>10.1016/0743-7315(89)90002-6]
	87	J. H. Reif , J. D. Tygar, Efficient parallel pseudorandom number generation, SIAM Journal on Computing, v.17 n.2, p.404-411, April 1988 [doi>10.1137/0217024]
	88	Ripley, B. D. The Lattice Structure of Pseudo-random Number Generators. In Proceedings of the Royal Society of London, 389 Ser. A, (1983) pp. 197-204.
	89	Brian D. Ripley, Stochastic simulation, John Wiley & Sons, Inc., New York, NY, 1987
	90	B. D. Ripley, Uses and abuses of statistical simulation, Mathematical Programming: Series A and B, v.42 n.1, p.53-68, April 1988 [doi>10.1007/BF01589392]
	91	Stern, J. Secret linear congruential generators are not cryptographically secure. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science (1987) pp. 42 l-426.
	92	Tausworthe, R. C. Random numbers generated by linear recurrence modulo two. Math. of Comput., 19 (1965) 201-209.
	93	Shu Tezuka, Walsh-spectral test for GFSR pseudorandom numbers, Communications of the ACM, v.30 n.8, p.731-735, Aug. 1987 [doi>10.1145/27651.27657]
	94	Shu Tezuka, On the discrepancy of GFSR pseudorandom numbers, Journal of the ACM (JACM), v.34 n.4, p.939-949, Oct. 1987 [doi>10.1145/31846.31848]
	95	Tezuka, S. On optimal GFSR pseudorandom number generators. Math. of Computat. 50, 182 (Apr. 1988) 531-533.
	96	Tezuka, S. Random number generation based on the polynomial airthmetic module two. Rep. RT- 0017, IBM Research, Tokyo Research Laboratory, Oct. 1989.
	97	Tezuka, S. Analysis of L'Ecuyer's combined random number generator. RT-5014, IBM Research, Tokyo Research Laboratory, Nov. 1989.
	98	Tindo, G. Automates cellulaires; apphcations B la modelisation de certains systemes discrets et a la conception d'une architecture parallele pour la generation de suites pseudo-aleatoires. These de doctorat en informatique, Universite de Nantes, France, Jan. 1990.
	99	Wichmann, B. A. and Hill, 1. D. An Efficient and portable pseudorandom number generator. Appl. Stat. 31 (1982) 188-190. Also see corrections and remarks in the same journal by Wichmann and Hill 33 123; (1984) McLeod 34 (1985) 198-200; Zeisel 35 (1986) 89.
	100	Brian Wichmann , David Hill, Building a random-number generator, BYTE, v.12 n.3, p.127-128, March 1987
	101	R. S. Wikramaratna, ACORN—A new method for generating sequences of uniformly distributed Pseudo-random numbers, Journal of Computational Physics, v.83 n.1, p.16-31, July 1989 [doi>10.1016/0021-9991(89)90221-0]