Abstract
We introduce TestU01, a software library implemented in the ANSI C language, and offering a collection of utilities for the empirical statistical testing of uniform random number generators (RNGs). It provides general implementations of the classical statistical tests for RNGs, as well as several others tests proposed in the literature, and some original ones. Predefined tests suites for sequences of uniform random numbers over the interval (0, 1) and for bit sequences are available. Tools are also offered to perform systematic studies of the interaction between a specific test and the structure of the point sets produced by a given family of RNGs. That is, for a given kind of test and a given class of RNGs, to determine how large should be the sample size of the test, as a function of the generator's period length, before the generator starts to fail the test systematically. Finally, the library provides various types of generators implemented in generic form, as well as many specific generators proposed in the literature or found in widely used software. The tests can be applied to instances of the generators predefined in the library, or to user-defined generators, or to streams of random numbers produced by any kind of device or stored in files. Besides introducing TestU01, the article provides a survey and a classification of statistical tests for RNGs. It also applies batteries of tests to a long list of widely used RNGs.
- Agarwal, R. C., Enenkel, R. F., Gustavson, F. G., Kothari, A., and m. Zubair. 2002. Fast pseudorandom-number generators with modulus 2k or 2k − 1 using fused multiply-add. IBM J. Res. and Dev. 46, 1, 97--116. Google ScholarDigital Library
- Anderson, T. W. and Darling, D. A. 1952. Asymptotic theory of certain goodness of fit criteria based on stochastic processes. Ann. Math. Stat. 23, 193--212.Google ScholarCross Ref
- Barker, E. and Kelsey, J. 2006. Recommendation for random number generation using deterministic random bit generators. SP-800-90, U.S. DoC/National Institute of Standards and Technology. http://csrc.nist.gov/publications/nistpubs/.Google Scholar
- Berlekamp, E. R. 1984. Algebraic Coding Theory. Aegean Park Press, Laguna Hills, CA.Google Scholar
- Bickel, P. J. and Breiman, L. 1983. Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test. Ann. Probab. 11, 1, 185--214.Google ScholarCross Ref
- Brent, R. P. 2004. Note on Marsaglia's xorshift random number generators. J. Statis. Softw. 11, 5, 1--4. http://www.jstatsoft.org/v11/i05/brent.pdf.Google ScholarCross Ref
- Brown, F. B. and Nagaya, Y. 2002. The MCNP5 random number generator. Tech. rep. LA-UR-02-3782, Los Alamos National Laboratory.Google Scholar
- Carter, G. D. 1989. Aspects of local linear complexity. Ph.D. thesis, University of London.Google Scholar
- Couture, R. and L'Ecuyer, P. 1994. On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Mathem. Comput. 62, 206, 798--808. Google Scholar
- Couture, R. and L'Ecuyer, P. 1997. Distribution properties of multiply-with-carry random number generators. Mathem. Comput. 66, 218, 591--607. Google Scholar
- Coveyou, R. R. 1969. Random number generation is too important to be left to chance. In Applied Probability and Monte Carlo Methods and Modern Aspects of Dynamics. Studies in Applied Mathematics 3. Society for Industrial and Applied Mathematics, Philadelphia, PA. 70--111.Google Scholar
- Daemen, J. and Rijmen, V. 2002. The Design of Rijndael. Springer-Verlag, Berlin, Germany. http://www.esat.kuleuven.ac.be/~rijmen/rijndael/. Google Scholar
- Darling, D. A. 1960. On the theorems of Kolmogorov-Smirnov. Theo. Probab. Applic. V, 4, 356--360.Google ScholarCross Ref
- Deng, L.-Y. 2005. Efficient and portable multiple recursive generators of large order. ACM Trans. Model. Comput. Simul. 15, 1, 1--13. Google ScholarDigital Library
- Deng, L.-Y. and Lin, D. K. J. 2000. Random number generation for the new century. Ame. Statis. 54, 2, 145--150.Google ScholarCross Ref
- Durbin, J. 1973. Distribution theory for tests based on the sample distribution function. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia, PA.Google Scholar
- Eichenauer, J. and Lehn, J. 1986. A nonlinear congruential pseudorandom number generator. Statistische Hefte 27, 315--326.Google ScholarCross Ref
- Eichenauer-Herrmann, J. 1992. Inversive congruential pseudorandom numbers: A tutorial. Inte. Statist. Rev. 60, 167--176.Google ScholarCross Ref
- Erdmann, E. D. 1992. Empirical tests of binary keystreams. M.S. thesis, Department of Mathematics, Royal Holloway and Bedford New College, University of London.Google Scholar
- Feller, W. 1968. An Introduction to Probability Theory. Vol. 1, 3rd Ed. John Wiley, New York, NY.Google Scholar
- Ferrenberg, A. M., Landau, D. P., and Wong, Y. J. 1992. Monte Carlo simulations: Hidden errors from “good” random number generators. Phy. Rev. Lett. 69, 23, 3382--3384.Google ScholarCross Ref
- Fishman, G. S. 1990. Multiplicative congruential random number generators with modulus 2β: An exhaustive analysis for β = 32 and a partial analysis for β = 48. Mathem. Comput. 54, 189 (Jan), 331--344.Google Scholar
- Fishman, G. S. 1996. Monte Carlo: Concepts, Algorithms, and Applications. Springer Series in Operations Research. Springer-Verlag, Berlin, Germany.Google ScholarCross Ref
- Fishman, G. S. and Moore III, L. S. 1986. An exhaustive analysis of multiplicative congruential random number generators with modulus 231 − 1. SIAM J. Sci. Statist. Comput. 7, 1, 24--45. Google ScholarDigital Library
- Földes, A. 1979. The limit distribution of the length of the longest head run. Period Math. Hung. 10, 4, 301--310.Google ScholarCross Ref
- Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Booth, M., and Rossi, F. 2004. GSL -- GNU Scientific Library: Reference manual. http://www.gnu.org/software/gsl/.Google Scholar
- Gammel, B. M. 2005. Matpack C++ Numerics and Graphics Library, Release 1.8.1. http://users.physik.tu-muenchen.de/gammel/matpack/index.html.Google Scholar
- Goldreich, O. 1999. Modern Cryptography, Probabilistic Proofs and Pseudo-Randomness. Springer-Verlag, Berlin, Germany. Google Scholar
- Good, I. J. 1953. The serial test for sampling numbers and other tests for randomness. In Proceedings of the Cambridge Philosophical Society 49, 276--284.Google ScholarCross Ref
- Gordon, L., Schilling, M. F., and Waterman, S. 1986. An extreme value theory for long head runs. Probab. Theo. Relat. Fields 72, 279--287.Google ScholarCross Ref
- Greenwood, R. E. 1955. Coupon collector's test for random digits. Math. Tables Aids Comput. 9, 1--5, 224, 229.Google ScholarCross Ref
- Hellekalek, P. 1995. Inversive pseudorandom number generators: Concepts, results, and links. In Proceedings of the 1995 Winter Simulation Conference, C. Alexopoulos, K. Kang, W. R. Lilegdon, and D. Goldsman, Eds. IEEE Press, 255--262. Google Scholar
- Hellekalek, P. 1998. Don't trust parallel Monte Carlo! In 12th Workshop on Parallel and Distributed Simulation. Banff, Canada. IEEE Computer Society, Los Alamitos, CA, 82--89. Google Scholar
- Hellekalek, P. and Wegenkittl, S. 2003. Empirical evidence concerning AES. ACM Trans. Model. Comput. Simul. 13, 4, 322--333. Google ScholarDigital Library
- Holian, B. L., Percus, O. E., Warnock, T. T., and Whitlock, P. A. 1994. Pseudorandom number generator for massively parallel molecular-dynamics simulations. Phys. Rev. E 50, 2, 1607--1615.Google ScholarCross Ref
- IBM 1968. System/360 Scientific Subroutine Package. Version III, Programmer's Manual. IBM, White Plains, New York.Google Scholar
- IMSL. 1997. IMSL STAT/LIBRARY. Visual Numerics Inc., Houston, TX. http://www.vni.com/books/dod/pdf/STATVol_2.pdf.Google Scholar
- Intel. 2003. Vector statistical library notes. Tech. rep. version 3, Intel Corporation. http://www.intel.com/software/products/mkl/docs/vslnotes.pdf.Google Scholar
- James, F. 1994. RANLUX: A Fortran implementation of the high-quality pseudorandom number generator of Lüscher. Comput. Phys. Comm. 79, 111--114.Google ScholarCross Ref
- Jenkins, B. 1996. ISAAC. in fast software encryption. In Proceedings of the 3rd International Workshop. Cambridge, UK, D. Gollmann, Ed. Lecture Notes in Computer Science, vol. 1039. Springer-Verlag, 41--49. http://burtleburtle.net/bob/rand/isaacafa.html. Google Scholar
- Kendall, M. G. and Babington-Smith, B. 1939. Second paper on random sampling numbers. J. Royal Statis. Soc. Suppl. 6, 51--61.Google ScholarCross Ref
- Kirkpatrick, S. and Stoll, E. 1981. A very fast shift-register sequence random number generator. J. Comput. Physics 40, 517--526.Google ScholarCross Ref
- Kirschenhofer, P., Prodinger, H., and Szpankowski, W. 1994. Digital search trees again revisited: The internal path length perspective. SIAM J. Comput. 23, 598--616. Google ScholarDigital Library
- Knuth, D. E. 1981. The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, 2nd Ed. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- Knuth, D. E. 1998. The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- Lagarias, J. C. 1993. Pseudorandom numbers. Statis. Sci. 8, 1, 31--39.Google ScholarCross Ref
- L'Ecuyer, P. 1988. Efficient and portable combined random number generators. Comm. ACM 31, 6, 742--749 and 774. (See also the correspondence in the same journal, 32, 8 (1989) 1019--1024.) Google ScholarDigital Library
- L'Ecuyer, P. 1990. Random numbers for simulation. Comm. ACM 33, 10, 85--97. Google ScholarDigital Library
- L'Ecuyer, P. 1992. Testing random number generators. In Proceedings of the 1992 Winter Simulation Conference. IEEE Press, 305--313. Google Scholar
- L'Ecuyer, P. 1994. Uniform random number generation. Ann. Operat. Res. 53, 77--120.Google ScholarCross Ref
- L'Ecuyer, P. 1996a. Combined multiple recursive random number generators. Operat. Res. 44, 5, 816--822.Google ScholarDigital Library
- L'Ecuyer, P. 1996b. Maximally equidistributed combined Tausworthe generators. Mathem. Comput. 65, 213, 203--213. Google Scholar
- L'Ecuyer, P. 1997a. Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9, 1, 57--60.Google ScholarDigital Library
- L'Ecuyer, P. 1997b. Tests based on sum-functions of spacings for uniform random numbers. J. Stat. Comput. Simul. 59, 251--269.Google ScholarCross Ref
- L'Ecuyer, P. 1999a. Good parameters and implementations for combined multiple recursive random number generators. Operat. Res. 47, 1, 159--164. Google ScholarDigital Library
- L'Ecuyer, P. 1999b. Tables of maximally equidistributed combined LFSR generators. Mathem. Comput. 68, 225, 261--269. Google Scholar
- L'Ecuyer, P. 2001. Software for uniform random number generation: Distinguishing the good and the bad. In Proceedings of the Winter Simulation Conference. IEEE Press, 95--105. Google Scholar
- L'Ecuyer, P. 2004. Random number generation. In Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, Eds. Springer-Verlag, Berlin, Germany. 35--70. Chapter II.2.Google Scholar
- L'Ecuyer, P. circa 2006. Uniform random number generation. In Stochastic Simulation, S. G. Henderson and B. L. Nelson, Eds. Handbooks of Operations Research and Management Science. Elsevier Science. To appear.Google Scholar
- L'Ecuyer, P. and Andres, T. H. 1997. A random number generator based on the combination of four LCGs. Mathem. Comput. Simul. 44, 99--107. Google ScholarDigital Library
- L'Ecuyer, P., Blouin, F., and Couture, R. 1993. A search for good multiple recursive random number generators. ACM Tran. Model. Comput. Simul. 3, 2, 87--98. Google ScholarDigital Library
- L'Ecuyer, P. and Buist, E. 2005. Simulation in Java with SSJ. In Proceedings of the Winter Simulation Conference. IEEE Press, 611--620. Google Scholar
- L'Ecuyer, P., Cordeau, J.-F., and Simard, R. 2000. Close-point spatial tests and their application to random number generators. Operat. Res. 48, 2, 308--317. Google ScholarDigital Library
- L'Ecuyer, P. and Granger-Piché, J. 2003. Combined generators with components from different families. Mathem. Comput Simul. 62, 395--404. Google ScholarDigital Library
- L'Ecuyer, P. and Hellekalek, P. 1998. Random number generators: Selection criteria and testing. In Random and Quasi-Random Point Sets, P. Hellekalek and G. Larcher, Eds. Lecture Notes in Statistics, vol. 138. Springer-Verlag, Berlin, Germany. 223--265.Google Scholar
- L'Ecuyer, P. and Simard, R. 1999. Beware of linear congruential generators with multipliers of the form a = ± 2q ± 2r. ACM Trans. Math. Soft. 25, 3, 367--374. Google ScholarDigital Library
- L'Ecuyer, P. and Simard, R. 2001. On the performance of birthday spacings tests for certain families of random number generators. Mathem. Comput. Simul. 55, 1--3, 131--137. Google Scholar
- L'Ecuyer, P., Simard, R., Chen, E. J., and Kelton, W. D. 2002. An object-oriented random-number package with many long streams and substreams. Operat. Res. 50, 6, 1073--1075. Google ScholarDigital Library
- L'Ecuyer, P., Simard, R., and Wegenkittl, S. 2002. Sparse serial tests of uniformity for random number generators. SIAM J. Scient. Comput. 24, 2, 652--668. Google ScholarDigital Library
- L'Ecuyer, P. and Touzin, R. 2000. Fast combined multiple recursive generators with multipliers of the form a = ± 2q ± 2r. In Proceedings of the Winter Simulation Conference, J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, Eds. IEEE Press, 683--689. Google Scholar
- L'Ecuyer, P. and Touzin, R. 2004. On the Deng-Lin random number generators and related methods. Statis. Comput. 14, 5--9. Google ScholarCross Ref
- Lewis, P. A. W., Goodman, A. S., and Miller, J. M. 1969. A pseudo-random number generator for the system/360. IBM Syst. J. 8, 136--143.Google ScholarDigital Library
- Liang, Y. and Whitlock, P. A. 2001. A new empirical test for parallel pseudo-random number generators. Mathem. Comput. Simul. 55, 1--3, 149--158. Google Scholar
- Lüscher, M. 1994. A portable high-quality random number generator for lattice field theory simulations. Comput. Physics Comm. 79, 100--110.Google ScholarCross Ref
- Maplesoft. 2006. Maple User Manual. Waterloo Maple Inc., Waterloo, Canada. http://www.maplesoft.com/products/maple/.Google Scholar
- Marsaglia, G. 1972. The structure of linear congruential sequences. In Applications of Number Theory to Numerical Analysis, S. K. Zaremba, Ed. Academic Press, 249--285.Google Scholar
- Marsaglia, G. 1985. A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland, Amsterdam, The Netherlands. 3--10.Google Scholar
- Marsaglia, G. 1996. DIEHARD: A battery of tests of randomness. http://stat.fsu.edu/~geo/diehard.html.Google Scholar
- Marsaglia, G. 1997. A random number generator for C. Posted to the electronic billboard sci.math.num-analysis.Google Scholar
- Marsaglia, G. 1999. Random numbers for C: The END? Posted to the electronic billboard sci.crypt.random-numbers.Google Scholar
- Marsaglia, G. 2002. Good 64-bit RNG's. Posted to the electronic billboard sci.crypt.random-numbers.Google Scholar
- Marsaglia, G. 2003. Xorshift RNGs. J. Statis. Soft. 8, 14, 1--6. http://www.jstatsoft.org/v08/i14/xorshift.pdf.Google Scholar
- Marsaglia, G., Ananthanarayanan, K., and Paul, N. 1973. How to use the McGill random number package SUPER-DUPER. Tech. rep., School of Computer Science, McGill University, Montreal, Canada.Google Scholar
- Marsaglia, G., Narasimhan, B., and Zaman, A. 1990. A random number generator for PC's. Comput. Physics Comm. 60, 345--349.Google ScholarCross Ref
- Marsaglia, G. and Tsang, W. W. 2002. Some difficult-to-pass tests of randomness. J. Statist. Soft. 7, 3, 1--9. http://www.jstatsoft.org/v07/i03/tuftests.pdf.Google ScholarCross Ref
- Marsaglia, G. and Tsay, L.-H. 1985. Matrices and the structure of random number sequences. Lin. Algebra Applic. 67, 147--156.Google ScholarCross Ref
- Marsaglia, G. and Zaman, A. 1991. A new class of random number generators. Ann. Appl. Proba. 1, 462--480.Google ScholarCross Ref
- Marsaglia, G. and Zaman, A. 1993a. The KISS generator. Tech. rep., Department of Statistics, University of Florida.Google Scholar
- Marsaglia, G. and Zaman, A. 1993b. Monkey tests for random number generators. Comput. Math. Applic. 26, 9, 1--10.Google ScholarCross Ref
- Mascagni, M. and Srinivasan, A. 2000. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. ACM Trans. Mathem. Soft. 26, 436--461. Google ScholarDigital Library
- Massey, J. L. 1969. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theor IT-15, 122--127.Google ScholarCross Ref
- MathSoft Inc. 2000. S-PLUS 6.0 Guide to Statistics. Vol. 2. Data Analysis Division, Seattle, WA.Google Scholar
- Matsumoto, M. and Kurita, Y. 1992. Twisted GFSR generators. ACM Trans. Model. Comput. Simul. 2, 3, 179--194. Google ScholarDigital Library
- Matsumoto, M. and Kurita, Y. 1994. Twisted GFSR generators II. ACM Trans. Model. Comput. Simul. 4, 3, 254--266. Google ScholarDigital Library
- Matsumoto, M. and Nishimura, T. 1998. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 1, 3--30. Google ScholarDigital Library
- Maurer, J., Abrahams, D., Dawes, B., and Rivera, R. 2004. Boost random number library. http://www.boost.org/libs/random/index.html.Google Scholar
- Maurer, U. M. 1992. A universal statistical test for random bit generators. J. Cryptol. 5, 2, 89--105. Google ScholarDigital Library
- Moler, C. 2004. Numerical Computing with MATLAB. SIAM, Philadelphia, PA.Google Scholar
- NAG. 2002. The NAG C Library Manual, Mark 7. The Numerical Algorithms Group. http://www.nag.co.uk/numeric/cl/manual/pdf/G05/g05cac.pdf and http://www.nag.co.uk/numeric/fl/manual/pdf/G05/g05kaf.pdf.Google Scholar
- Niederreiter, H. 1991. The linear complexity profile and the jump complexity of keystream sequences. In Advances in Cryptology: Proceedings of EUROCRYPT'90. Springer-Verlag, Berlin, Germany, 174--188. Google Scholar
- Niederreiter, H. 1992. Random number generation and quasi-monte carlo methods. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 63. SIAM, Philadelphia, PA. Google ScholarDigital Library
- NIST. 2001. Advanced encryption standard (AES). FIPS-197, U.S. DoC/National Institute of Standards and Technology. http://csrc.nist.gov/CryptoToolkit/tkencryption.html.Google Scholar
- NIST. 2002. Secure hash standard (SHS). FIPS-186-2, with change notice added in february 2004, U.S. DoC/National Institute of Standards and Technology. http://csrc.nist.gov/CryptoToolkit/tkhash.html.Google Scholar
- Panneton, F. and L'Ecuyer, P. 2005. On the xorshift random number generators. ACM Trans. Model. Comput. Simul. 15, 4, 346--361. Google ScholarDigital Library
- Panneton, F., L'Ecuyer, P., and Matsumoto, M. 2006. Improved long-period generators based on linear recurrences modulo 2. ACM Trans. Math. Soft. 32, 1, 1--16. Google ScholarDigital Library
- Percus, O. E. and Whitlock, P. A. 1995. Theory and application of Marsaglia's monkey test for pseudorandom number generators. ACM Trans. Model. Comput. Simul. 5, 2, 87--100. Google ScholarDigital Library
- Press, W. H. and Teukolsky, S. A. 1992. Numerical Recipes in C. Cambridge University Press, Cambridge, UK.Google Scholar
- Project, T. G. 2003. R: An Environment for Statistical Computing and Graphics. The Free Software Foundation. Version 1.6.2. http://www.gnu.org/directory/GNU/R.html.Google Scholar
- Read, T. R. C. and Cressie, N. A. C. 1988. Goodness-of-Fit Statistics for Discrete Multivariate Data. Springer Series in Statistics. Springer-Verlag, Berlin, Germany.Google Scholar
- Rijmen, V., Bosselærs, A., and Barreto, P. 2000. Optimised ANSI C code for the Rijndael cipher (now AES). Public domain software.Google Scholar
- Ripley, B. D. 1990. Thoughts on pseudorandom number generators. J. Comput. Appl. Mathem. 31, 153--163. Google ScholarCross Ref
- Ripley, B. D. and Venables, W. N. 1994. Modern Applied Statistics with S-Plus. Springer-Verlag, Berlin, Germany.Google Scholar
- Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., and Vo, S. 2001. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST special publication 800-22, National Institute of Standards and Technology (NIST), Gaithersburg, MD. http://csrc.nist.gov/rng/.Google Scholar
- Rukhin, A. L. 2001. Testing randomness: A suite of statistical procedures. Theo. Probab. Applic. 45, 1, 111--132.Google ScholarCross Ref
- Ryabko, B. Y., Monarev, V. A., and Shokin, Y. I. 2005. A new type of attack on block ciphers. Probl. Informa. Transmis. 41, 4, 385--394. Google ScholarDigital Library
- Ryabko, B. Y., Stognienko, V. S., and Shokin, Y. I. 2004. A new test for randomness and its application to some cryptographic problems. J. Statist. Plan. Infer. 123, 365--376.Google ScholarCross Ref
- SciFace Software. 2004. MuPAD. SciFace Software GmbH & Co.KG, Paderborn, Germany. http://www.mupad.de/home.html.Google Scholar
- Sinclair, C. D. and Spurr, B. D. 1988. Approximations to the distribution function of the Anderson-Darling test statistic. J. Amer. Statist. Ass. 83, 404, 1190--1191.Google Scholar
- Stephens, M. A. 1970. Use of the Kolmogorov-Smirnov, Cramér-Von Mises and related statistics without extensive tables. J. Royal Statis. Soc., Series B 33, 1, 115--122.Google Scholar
- Stephens, M. S. 1986a. Tests based on EDF statistics. In Goodness-of-Fit Techniques, R. B. D'Agostino and M. S. Stephens, Eds. Marcel Dekker, New York, NY.Google Scholar
- Stephens, M. S. 1986b. Tests for the uniform distribution. In Goodness-of-Fit Techniques, R. B. D'Agostino and M. S. Stephens, Eds. Marcel Dekker, New York, NY, 331--366.Google Scholar
- Takashima, K. 1996. Last visit time tests for pseudorandom numbers. J. Japan. Soc. Comp. Satist. 9, 1, 1--14.Google Scholar
- Tezuka, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer Academic Publishers, Norwell, MA.Google Scholar
- Tezuka, S., L'Ecuyer, P., and Couture, R. 1994. On the add-with-carry and subtract-with-borrow random number generators. ACM Trans. Model. Comput. Simula. 3, 4, 315--331. Google ScholarDigital Library
- Tootill, J. P. R., Robinson, W. D., and Eagle, D. J. 1973. An asymptotically random Tausworthe sequence. J. ACM 20, 469--481. Google ScholarDigital Library
- Ugrin-Sparac, G. 1991. Stochastic investigations of pseudo-random number generators. Comput. 46, 53--65. Google ScholarDigital Library
- Vattulainen, I., Ala-Nissila, T., and Kankaala, K. 1995. Physical models as tests of randomness. Physic. Rev. E 52, 3, 3205--3213.Google ScholarCross Ref
- Wang, M. Z. 1997. Linear complexity profiles and jump complexity. Inform. Proces. Let. 61, 165--168. Google ScholarDigital Library
- Wegenkittl, S. 1998. Generalized &phis;-divergence and frequency analysis in Markov chains. Ph.D. thesis, University of Salzburg. http://random.mat.sbg.ac.at/team/.Google Scholar
- Wegenkittl, S. 2001. Entropy estimators and serial tests for ergodic chains. IEEE Trans. Inform. Theo. 47, 6, 2480--2489. Google ScholarDigital Library
- Wegenkittl, S. 2002. A generalized &phis;-divergence for asymptotically multivariate normal models. J. Multivari. Anal. 83, 288--302.Google ScholarCross Ref
- Wichmann, B. A. and Hill, I. D. 1982. An efficient and portable pseudo-random number generator. App. Statis. 31, 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 ScholarCross Ref
- Wu, P.-C. 1997. Multiplicative, congruential random number generators with multiplier ± 2k1 ± 2k1 and modulus 2p − 1. ACM Trans. Mathem. Softw. 23, 2, 255--265. Google ScholarDigital Library
- Ziff, R. M. 1998. Four-tap shift-register-sequence random-number generators. Comput. Physics 12, 4, 385--392. Google ScholarDigital Library
- Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans. on Inform. Theo. 24, 5, 530--536.Google ScholarCross Ref
Index Terms
- TestU01: A C library for empirical testing of random number generators
Recommendations
Testing parallel random number generators
Monte Carlo computations are considered easy to parallelize. However, the results can be adversely affected by defects in the parallel pseudorandom number generator used. A parallel pseudorandom number generator must be tested for two types of ...
Random Sequences in Vehicle Routing Problem
Numerical Methods and ApplicationsAbstractIn this paper, we study the Capacitated Vehicle Routing Problem (CVRP) and implemented a simulation-based algorithm with different random number generators. The Binary-CWS-MCS algorithm has been integrated with six different random number ...
Occupancy Numbers in Testing Random Number Generators
The classical occupancy problem where n balls are placed in N cells is used for testing of random number generators. We show that the statistics of appropriately chosen occupancy numbers are incompatible with the statistics of manypseudorandom number ...
Comments