×

Good random number generators are (not so) easy to find. (English) Zbl 0931.65001

Summary: Every random number generator has its advantages and deficiencies. There are no “safe” generators. The practitioner’s problem is how to decide which random number generator will suit his needs best. In this paper, we will discuss criteria for good random number generators: theoretical support, empirical evidence and practical aspects. We will study several recent algorithms that perform better than most generators in actual use. We will compare the different methods and supply numerical results as well as selected pointers and links to important literature and other sources.

MSC:

65C10 Random number generation in numerical analysis

Software:

C-RAND; PRNGlib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, S. L.: Random number generation on vector supercomputers and other advanced architectures. SIAM review 32, 221-251 (1990) · Zbl 0708.65004
[2] Compagner, A.: Operational conditions for random-number generation. Phys. review E 52, 5634-5645 (1995)
[3] Coveyou, R. R.; Macpherson, R. D.: Fourier analysis of uniform random number generators. J. assoc. Comput. Mach 14, 100-119 (1967) · Zbl 0155.22801
[4] De Matteis, A.; Eichenauer-Herrmann, J.; Grothe, H.: Computation of critical distances within multiplicative congruential pseudorandom number sequences. J. comp. Appl. math. 39, 49-55 (1992) · Zbl 0745.65005
[5] De Matteis, A.; Pagnutti, S.: Long-range correlations in linear and non-linear random number generators. Parallel computing 14, 207-210 (1990) · Zbl 0712.65005
[6] De Matteis, A.; Pagnutti, S.: Critical distances in pseudorandom sequences generated with composite moduli. Intern. J. Computer math. 43, 189-196 (1992) · Zbl 0758.65003
[7] L. Devroye, Non-Uniform Random Variate Generation, Springer, New York, 1986 · Zbl 0593.65005
[8] C. Döll, Die digitale Inversionsmethode zur Erzeugung von Pseudozufallszahlen, Master’s thesis, Fachbereich Mathematik, Technische Hochschule Darmstadt, 1996
[9] Eichenauer, J.; Lehn, J.: A non-linear congruential pseudo random number generator. Statist. papers 27, 315-326 (1986) · Zbl 0607.65001
[10] Eichenauer-Herrmann, J.: Explicit inversive congruential pseudorandom numbers: the compound approach. Computing 51, 175-182 (1993) · Zbl 0787.65004
[11] Eichenauer-Herrmann, J.: Statistical independence of a new class of inversive congruential pseudorandom numbers. Math. comp. 60, 375-384 (1993) · Zbl 0795.65002
[12] Eichenauer-Herrmann, J.: Compound nonlinear congruential pseudorandom numbers. Mh. math. 117, 213-222 (1994) · Zbl 0803.65003
[13] K. Entacher, A collection of selected pseudorandom number generators with linear structures, Report, The pLab Group, Department of Mathematics, University of Salzburg, 1996
[14] Fishman, G. S.: 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, 331-344 (1990) · Zbl 0686.65004
[15] Fishman, G. S.; Moore, L. R.: A statistical evaluation of multiplicative congruential random number generators with modulus 231-1. J. amer. Statist. assoc. 77, 129-136 (1982) · Zbl 0477.65004
[16] G.S. Fishman, L.R. Moore III, An exhaustive analysis of multiplicative congruential random number generators with modulus 231-1, SIAM J. Sci. Statist. Comput., 7, 24–45, 1986. Erratum, ibid, 7, 1058, 1986 · Zbl 0603.65003
[17] P. Hellekalek, Inversive pseudorandom number generators: concepts, results, and links, in: C. Alexopoulos, K. Kang, W.R. Lilegdon, D. Goldsman (Eds.), Proceedings of the 1995 Winter Simulation Conference, 1995, pp. 255–262
[18] P. Hellekalek, On correlation analysis of pseudorandom numbers, Proceedings of the Second International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Salzburg, July 9–12, 1996, Lecture Notes in Statistics, Springer, New York, 1997, to appear · Zbl 0885.65005
[19] P. Hellekalek, H. Leeb, Dyadic diaphony, Acta Arith., 1996, to appear
[20] P. Hellekalek, H. Niederreiter, The weighted spectral test: diaphony, 1996, Submitted to ACM Trans. Modeling and Computer Simulation · Zbl 0921.11038
[21] M. Hennecke, Random number generators homepage, http://www.uni-karlsruhe.de/\simRNG/ · Zbl 0878.65007
[22] F. James, J. Hoogland, R. Kleiss, Multidimensional sampling for simulation and integration: measures, discrepancies, and quasi-random numbers, Preprint submitted to Computer Physics Communications, 1996 · Zbl 0927.65041
[23] B. Johnson, Radix-b extensions to some common empirical tests for pseudo-random number generators, To appear in ACM Trans. Modeling and Computer Simulation, 1996 · Zbl 0887.65004
[24] Kankaala, K.; Ala-Nissila, T.; Vattulainen, I.: Bit-level correlations in some pseudorandom number generators. Phys. rev. E 48, 4211-4214 (1993) · Zbl 0873.65004
[25] Kiefer, J.: On large deviations of the empiric d.f. Of vector chance variables and a law of the iterated logarithm. Pacific J. Math. 11, 649-660 (1961) · Zbl 0119.34904
[26] D.E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, Mass., 2nd ed., 1981 · Zbl 0477.65002
[27] Lagarias, J. C.: Pseudorandom numbers. Statistical science 8, 31-39 (1993)
[28] P. L’Ecuyer, Testing random number generators, in: J.J. Swain et al., (Ed.), Proc. 1992 Winter Simulation Conference (Arlington, Va., 1992), pp. 305–313, IEEE Press, Piscataway, NJ, 1992
[29] P. L’Ecuyer, Bad lattice structures for vectors of non-successive values produced by some linear recurrences, 1994, to appear in ORSA J. on Computing
[30] L’ecuyer, P.: Uniform random number generation. Ann. oper. Res. 53, 77-120 (1994) · Zbl 0843.65004
[31] P. L’Ecuyer, Random number generators, in: S. Gass, C. Harris (Eds.), Encyclopedia of Operations Research and Management Science, Kluwer Academic Publishers, 1995
[32] P. L’Ecuyer, Combined multiple-recursive random number generators, To appear in Operations Res. 44, 1996
[33] L’ecuyer, P.: Maximally equidistributed combined tausworthe generators. Math. comp. 65, 203-213 (1996) · Zbl 0853.65007
[34] P. L’Ecuyer, Random number generation, In Jerry Banks (Ed.), Handbook on Simulation, Wiley, New York, 1997
[35] L’ecuyer, P.; Blouin, F.; Couture, R.: A search for good multiple recursive random number generators. ACM trans. Model. comput. Simulation 3, 87-98 (1993) · Zbl 0842.65004
[36] P. L’Ecuyer, A. Compagner, J.-F. Cordeau, Entropy tests for random number generators, Submitted to ACM Trans, Modeling and Computer Simulation, 1996
[37] P. L’Ecuyer, J.-F. Cordeau, Close-point spatial tests for random number generators, draft version, 1996
[38] L’ecuyer, P.; Coté, S.: Implementing a random number package with splitting facilities. ACM trans. Math. software 17, 98-111 (1991) · Zbl 0900.65008
[39] P. L’Ecuyer, R. Couture, An implementation of the lattice and spectral tests for multiple recursive linear random number generators, INFORMS J. Comput., 1996, To appear
[40] H. Leeb, Random numbers for computer simulation. Master’s thesis, Institut für Mathematik, Universität Salzburg, Austria, 1995, Available from http://random.mat.sbg.ac.at/
[41] H. Leeb, A weak law for diaphony, Rist++13, Research Institute for Software Technology, University of Salzburg, 1996
[42] H. Leeb, S. Wegenkittl, Inversive and linear congruential pseudorandom number generators in empirical tests, To appear in ACM Trans. Modeling and Computer Simulation, 1996 · Zbl 0885.68149
[43] O. Lendl, Explicit inversive pseudorandom numbers. Master’s thesis, Institut für Mathematik, Universität Salzburg, Austria, 1996, Available from http://random.mat.sbg.ac.at/
[44] Maclaren, N. M.: A limit on the usable length of a pseudorandom sequence. J. statist. Comput. simul. 42, 47-54 (1992)
[45] G. Marsaglia, A current view of random number generators, in: L. Brillard (Ed.), Computer Science and Statistics: The Interface, Amsterdam, Elsevier Science Publishers B.V. (North Holland), 1985, pp. 3–10
[46] Marsaglia, G.; Zaman, A.: A new class of random number generators. Ann. appl. Prob. 1, 462-480 (1991) · Zbl 0733.65005
[47] M. Mascagni, M.L. Robinson, D.V. Pryor, S.A. Cuccaro, Parallel pseudorandom number generation using additive lagged-Fibonacci recursions, Technical report, Supercomputing Research Center, Institute for Defense Analyses, 1994 · Zbl 0843.11037
[48] N. Masuda, F. Zimmermannn, PRNGlib: a parallel random number generator library. Tachnical report, Swiss Center for Scientific Computing, 1996, Available from http://www.cscs.ch /Official/Publications.html
[49] Matsumoto, M.; Kurita, Y.: Twisted GFSR generators. ACM trans. Model. comput. Simul. 2, 179-194 (1992) · Zbl 0849.94014
[50] Matsumoto, M.; Kurita, Y.: Twisted GFSR generators II. ACM trans. Model. comput. Simul. 4, 254-266 (1994) · Zbl 0849.94015
[51] Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. amer. Math. soc. 84, 957-1041 (1978) · Zbl 0404.65003
[52] H. Niederreiter, New methods for pseudorandom number and pseudorandom vector generation, in: J.J. Swain et al., (Ed.), Proc. 1992 Winter Simulation Conference (Arlington, Va., 1992), IEEE Press, Piscataway, NJ, 1992, pp. 264–269 · Zbl 0849.11055
[53] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992 · Zbl 0761.65002
[54] Niederreiter, H.: On a new class of pseudorandom numbers for simulation methods. J. comp. Appl. math. 56, 159-167 (1994) · Zbl 0823.65010
[55] H. Niederreiter, New developments in uniform pseudorandom number and vector generation, in: H. Niederreiter, P.J.-S. Shiue, (Eds.), Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 106 of Lecture Notes in Statistics, Springer, New York, 1995, pp. 87–120 · Zbl 0893.11030
[56] D.V. Pryor, S.A. Cuccaro, M. Mascagni, M.L. Robinson, Implementation and usage of a portable and reproducible parallel pseudorandom number generator, Technical report, Supercomputing Research Center, Institute for Defense Analyses, 1994 · Zbl 0842.65005
[57] B.D. Ripley, Stochastic Simulation, John Wiley, New York, 1987 · Zbl 0613.65006
[58] K. Schaber, Digital inversive congruential generators. Master’s thesis, Institut für Mathematik, Universität Salzburg, Austria, 1997, Available from http://random.mat.sbg.ac.at/
[59] E. Stadlober, R. Kremer, Sampling from discrete and continuous distributions with c-Rand, in: G. Pflug, U. Dieter (Eds.), Simulation and Optimization, volume 374 of Lecture Notes in Economics and Math. Systems, Springer, Berlin, 1992, pp. 154–162 · Zbl 0757.65004
[60] E. Stadlober, F. Niederl, C-Rand: a package for generating nonuniform random variates, In Compstat ’94, Software Descriptions, 1994, pp. 63–64
[61] S. Tezuka, Uniform Random Numbers: Theory and Practice, Kluwer Academic Publisher, Norwell, Mass., 1995 · Zbl 0841.65004
[62] Vattulainen, I.; Ala-Nissila, T.; Kankaala, K.: Physical models as tests of randomness. Phys. rev. E 52, 3205-3214 (1995) · Zbl 0873.65004
[63] S. Wegenkittl, Empirical testing of pseudorandom number generators, Master’s thesis, Institut für Mathematik, Universität Salzburg, Austria, 1995, Available from http://random.mat.sbg.ac.at/
[64] P. Winker, K.-T. Fang, Application of threshold accepting to the evaluation of the discrepancy of a set of points, Research report, Universität Konstanz, 1995 · Zbl 0888.65021
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.