×

zbMATH — the first resource for mathematics

Spectral analysis of the MIXMAX random number generators. (English) Zbl 07284458
Summary: We study the lattice structure of random number generators of the MIXMAX family, a class of matrix linear congruential generators that produces a vector of random numbers at each step. The design of these generators was inspired by Kolmogorov \(K\)-systems over the unit torus in the real space, for which the transition function is measure preserving and produces a chaotic behavior. In actual implementations, however, the state space is a finite set of rational vectors, and the MIXMAX has a lattice structure just like linear congruential and multiple recursive generators. Its matrix entries were also selected in a special way to allow a fast implementation, and this has an impact on the lattice structure. We study this lattice structure for vectors of successive and nonsuccessive output values in various dimensions. We show in particular that for coordinates at specific lags not too far apart, in three dimensions, or if we construct points of \(k+2\) or more successive values from the beginning of an output vector of size \(k\), all the nonzero points lie in only two hyperplanes. This is reminiscent of the behavior of lagged-Fibonacci and add-with-carry/subtract-with-borrow generators. And even if we skip the output coordinates involved in this bad structure, other highly structured projections often remain, depending on the choice of parameters. We show that empirical statistical tests can easily detect this structure.
MSC:
65C10 Random number generation in numerical analysis
Software:
MIXMAX; RANLUX; TestU01
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Afflerbach L, Grothe H (1988) The lattice structure of pseudo-random vectors generated by matrix generators. J. Comput. Appl. Math. 23(1):127-131.Crossref, Google Scholar · Zbl 0658.65006
[2] Akopov NZ, Savvidy GK, Savvidy NGTA (1991) Matrix generators for pseudorandom numbers. J. Comput. Phys. 97(2):573-579.Crossref, Google Scholar · Zbl 0748.65006
[3] Conway JH, Sloane NJA (1999) Sphere Packings, Lattices and Groups. Grundlehren der Mathematischen Wissenschaften, vol. 290, 3rd ed. (Springer-Verlag, New York).Crossref, Google Scholar
[4] Couture R, L’Ecuyer P (1994) On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Math. Comput. 62(206):798-808.Crossref, Google Scholar · Zbl 0803.65005
[5] Couture R, L’Ecuyer P (1996) Orbits and lattices for linear random number generators with composite moduli. Math. Comput. 65(213):189-201.Crossref, Google Scholar · Zbl 0851.65005
[6] Coveyou RR, MacPherson RD (1967) Fourier analysis of uniform random number generators. J. ACM 14(1):100-119.Crossref, Google Scholar · Zbl 0155.22801
[7] Ferrenberg AM, Landau DP, Wong YJ (1992) Monte Carlo simulations: Hidden errors from “good” random number generators. Phys. Rev. Lett. 69(23):3382-3384.Crossref, Google Scholar
[8] Fincke U, Pohst M (1985) Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170):463-471.Crossref, Google Scholar · Zbl 0556.10022
[9] Grothe H (1988) Matrixgeneratoren zur erzeugung gleichverteilter pseudozufallsvektoren. Dissertation, Technische Hochschule, Darmstadt, Germany.Google Scholar · Zbl 0652.65008
[10] James F (1994) RANLUX: A Fortran implementation of the high-quality pseudorandom number generator of Lüscher. Comput. Phys. Commun. 79(1):111-114.Crossref, Google Scholar · Zbl 0879.65003
[11] Knuth DE (1998) The Art of Computer Programming: Seminumerical Algorithms, vol. 2, 3rd ed. (Addison-Wesley, Reading, MA).Google Scholar
[12] L’Ecuyer P (1990) Random numbers for simulation. Commun. ACM 33(10):85-97.Crossref, Google Scholar
[13] L’Ecuyer P (1994) Uniform random number generation. Ann. Oper. Res. 53(1):77-120.Crossref, Google Scholar · Zbl 0843.65004
[14] L’Ecuyer P (1997) Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9(1):57-60.Link, Google Scholar · Zbl 0894.65004
[15] L’Ecuyer P (1999) Tables of linear congruential generators of different sizes and good lattice structure. Math. Comput. 68(225):249-260. Errata accessed October 10, 2018, http://www.iro.umontreal.ca/∼lecuyer/myftp/papers/latrules99Errata.pdf.Crossref, Google Scholar · Zbl 0917.65002
[16] L’Ecuyer P (2006) Uniform random number generation. Henderson SG, Nelson BL, eds. Simulation, Handbooks in Operations Research and Management Science (Elsevier, Amsterdam), 55-81.Crossref, Google Scholar
[17] L’Ecuyer P (2012) Random number generation. Gentle JE, Haerdle W, Mori Y, eds. Handbook of Computational Statistics, 2nd ed. (Springer-Verlag, Berlin), 35-71.Crossref, Google Scholar
[18] L’Ecuyer P (2017) History of uniform random number generation. Proc. 2017 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 202-230.Crossref, Google Scholar
[19] L’Ecuyer P, Couture R (1997) An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS J. Comput. 9(2):206-217.Link, Google Scholar · Zbl 0889.65004
[20] L’Ecuyer P, Simard R (2001) On the performance of birthday spacings tests for certain families of random number generators. Math. Comput. Simul. 55(1-3):131-137.Crossref, Google Scholar · Zbl 0981.65008
[21] L’Ecuyer P, Simard R (2007) TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Software 33(4):Article No. 22.Crossref, Google Scholar · Zbl 1365.65008
[22] L’Ecuyer P, Simard R (2014) On the lattice structure of a special class of multiple recursive random number generators. INFORMS J. Comput. 26(2):449-460.Link, Google Scholar · Zbl 1304.65006
[23] L’Ecuyer P, Touzin R (2004) On the Deng-Lin random number generators and related methods. Statist. Comput. 14(1):5-9.Crossref, Google Scholar
[24] L’Ecuyer P, Simard R, Wegenkittl S (2002) Sparse serial tests of uniformity for random number generators. SIAM J. Sci. Comput. 24(2):652-668.Crossref, Google Scholar · Zbl 1037.62006
[25] L’Ecuyer P, Munger D, Oreshkin B, Simard R (2017) Random numbers for parallel computers: Requirements and methods, with emphasis on GPUs. Math. Comput. Simul. 135:3-17.Crossref, Google Scholar
[26] Lüscher M (1994) A portable high-quality random number generator for lattice field theory simulations. Comput. Phys. Commun. 79(1):100-110.Crossref, Google Scholar · Zbl 0879.65002
[27] Marsaglia G (1968) Random numbers fall mainly in the planes. Proc. Natl. Acad. Sci. USA 60:25-28.Crossref, Google Scholar · Zbl 0172.21002
[28] Marsaglia G, Zaman A (1991) A new class of random number generators. Ann. Appl. Probab. 1(3):462-480.Crossref, Google Scholar · Zbl 0733.65005
[29] Niederreiter H (1986) A pseudorandom vector generator based on finite field arithmetic. Math. Jpn. 31:759-774.Google Scholar · Zbl 0619.65002
[30] Savvidy GK, Ter-Arutyuntan-Savvidy NG (1991) On the Monte Carlo simulation of physical systems. J. Comput. Phys. 97(2):566-572.Crossref, Google Scholar · Zbl 0761.65003
[31] Savvidy KG (2015) The MIXMAX random number generator. Comput. Phys. Commun. 196:161-165.Crossref, Google Scholar · Zbl 1360.65031
[32] Savvidy KG (2017) MIXMAX manual. Accessed October 10, 2018, https://www.hepforge.org/archive/mixmax/MANUAL.pdf.Google Scholar
[33] Savvidy KG, Savvidy GK (2016) Spectrum and entropy of C-systems MIXMAX random number generator. Chaos Solitons Fractals 91:33-38.Crossref, Google Scholar · Zbl 1372.37060
[34] Tahmi E (1982) Contribution aux générateurs de valeurs aléatoires. Dissertation, Université des Sciences et Technologies Houari Boumédienne, Algeria.Google Scholar
[35] Tezuka S, L’Ecuyer P (1992) An analysis of add-with-carry and subtract-with-borrow generators. Proc. 1992 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 443-447.Crossref, Google Scholar
[36] Tezuka S, · Zbl 0843.65003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.