×

zbMATH — the first resource for mathematics

Conversion of mersenne twister to double-precision floating-point numbers. (English) Zbl 07316677
Summary: The 32-bit Mersenne Twister generator MT19937 is a widely used random number generator. To generate numbers with more than 32 bits in bit length, and particularly when converting into 53-bit double-precision floating-point numbers in \([0, 1)\) in the IEEE 754 format, the typical implementation concatenates two successive 32-bit integers and divides them by a power of 2. In this case, the 32-bit MT19937 is optimized in terms of its equidistribution properties (the so-called dimension of equidistribution with \(v\)-bit accuracy) under the assumption that one will mainly be using 32-bit output values, and hence the concatenation sometimes degrades the dimension of equidistribution compared with the simple use of 32-bit outputs. In this paper, we analyze such phenomena by investigating hidden \(\mathbb{F}_2\)-linear relations among the bits of high-dimensional outputs. Accordingly, we report that MT19937 with a specific lag set fails several statistical tests, such as the overlapping collision test, matrix rank test, and Hamming independence test.
MSC:
65C Probabilistic methods, stochastic differential equations
65 Numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Couture, R.; L’Ecuyer, P., Lattice computations for random numbers, Math. Comp., 69, 230, 757-765 (2000) · Zbl 0952.65003
[2] Haramoto, H.; Matsumoto, M.; Nishimura, T., Computing conditional probabilities for \(F_2\)-linear pseudorandom bit generators by splitting MacWilliams identity, Int. J. Pure Appl. Math., 38, 1, 29-42 (2007) · Zbl 1134.65008
[3] Haramoto, H.; Matsumoto, M.; Nishimura, T.; Otsuka, Y., A non-empirical test on the second to the sixth least significant bits of pseudorandom number generators, (Monte Carlo and quasi-Monte Carlo Methods 2012. Monte Carlo and quasi-Monte Carlo Methods 2012, Springer Proc. Math. Stat., vol. 65 (2013), Springer: Springer Heidelberg), 417-426 · Zbl 1302.65023
[4] Harase, S., An efficient lattice reduction method for \(F_2\)-linear pseudorandom number generators using Mulders and Storjohann algorithm, J. Comput. Appl. Math., 236, 2, 141-149 (2011) · Zbl 1229.65024
[5] Harase, S., On the \(F_2\)-linear relations of Mersenne Twister pseudorandom number generators, Math. Comput. Simulation, 100, 103-113 (2014)
[6] Harase, S.; Kimoto, T., Implementing 64-bit maximally equidistributed \(F_2\)-linear generators with Mersenne prime period, ACM Trans. Math. Software, 44, 3, 30:1-30:11 (2018) · Zbl 06920093
[9] Knuth, D. E., (The Art of Computer Programming. The Art of Computer Programming, Seminumerical Algorithms, vol. 2 (1997), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA) · Zbl 0895.68055
[10] L’Ecuyer, P., Bad lattice structures for vectors of nonsuccessive values produced by some linear recurrences, INFORMS J. Comput., 9, 1, 57-60 (1997) · Zbl 0894.65004
[11] L’Ecuyer, P., Tables of maximally equidistributed combined LFSR generators, Math. Comp., 68, 225, 261-269 (1999) · Zbl 0917.65003
[12] L’Ecuyer, P.; Cordeau, J. F.; Simard, R., Close-point spatial tests and their application to random number generators, Oper. Res., 48, 2, 308-317 (2000) · Zbl 1106.65301
[13] L’Ecuyer, P.; Panneton, F., \(F_2\)-linear random number generators, (Alexopoulos, C.; Goldsman, D.; Wilson, J. R., Advancing the Frontiers of Simulation: A Festschrift in Honor of George Samuel Fishman (2009), Springer-Verlag: Springer-Verlag New York), 169-193
[14] L’Ecuyer, P.; Simard, R., Beware of linear congruential generators with multipliers of the form \(a = \pm 2^q \pm 2^r\), ACM Trans. Math. Softw., 25, 3, 367-374 (1999) · Zbl 0964.65002
[15] L’Ecuyer, P.; Simard, R., On the performance of birthday spacings tests with certain families of random number generators, Math. Comput. Simulation, 55, 1-3, 131-137 (2001), The Second IMACS Seminar on Monte Carlo Methods (Varna, 1999) · Zbl 0981.65008
[16] L’Ecuyer, P.; Simard, R., TestU01: a C library for empirical testing of random number generators, ACM Trans. Math. Softw., 33, 4, 22 (2007), 40 · Zbl 1365.65008
[17] L’Ecuyer, P.; Simard, R., On the lattice structure of a special class of multiple recursive random number generators, INFORMS J. Comput., 26, 3, 449-460 (2014) · Zbl 1304.65006
[18] L’Ecuyer, P.; Simard, R.; Wegenkittl, S., Sparse serial tests of uniformity for random number generators, SIAM J. Sci. Comput., 24, 2, 652-668 (2002) · Zbl 1037.62006
[19] L’Ecuyer, P.; Touzin, R., On the Deng-Lin random number generators and related methods, Stat. Comput., 14, 5-9 (2004)
[20] Marsaglia, G., A current view of random number generators, (Computer Science and Statistics, Sixteenth Symposium on the Interface (1985), Elsevier Science Publisher, North-Holland: Elsevier Science Publisher, North-Holland Amsterdam, The Netherlands), 3-10
[21] Matsumoto, M.; Nishimura, T., Mersenne twister: a \(623\)-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 1, 3-30 (1998) · Zbl 0917.65005
[22] Matsumoto, M.; Nishimura, T., A nonempirical test on the weight of pseudorandom number generators, (Monte Carlo and quasi-Monte Carlo Methods, 2000 (Hong Kong) (2002), Springer: Springer Berlin), 381-395 · Zbl 1002.65010
[23] Matsumoto, M.; Saito, M.; Haramoto, H.; Nishimura, T., Pseudorandom number generation: Impossibility and compromise, J. Univ. Comput. Sci., 12, 6, 672-690 (2006)
[24] Nishimura, T., Tables of 64-bit Mersenne twisters, ACM Trans. Model. Comput. Simul., 10, 4, 348-357 (2000) · Zbl 1390.65014
[25] Saito, M.; Matsumoto, M., SIMD-oriented fast mersenne twister: a 128-bit pseudorandom number generator, (Keller, A.; Heinrich, S.; Niederreiter, H., Monte Carlo and quasi-Monte Carlo Methods 2006 (2008), Springer-Verlag: Springer-Verlag Berlin), 607-622, http://www.math.sci.hiroshima-u.ac.jp/ m-mat/MT/SFMT/index.html · Zbl 1141.65319
[26] Saito, M.; Matsumoto, M., A PRNG specialized in double precision floating point numbers using an affine transition, (Monte Carlo and quasi-Monte Carlo Methods 2008 (2009), Springer: Springer Berlin), 589-602 · Zbl 1184.65013
[27] Tootill, J. P.R.; Robinson, W. D.; Eagle, D. J., An asymptotically random tausworthe sequence, J. ACM, 20, 3, 469-481 (1973) · Zbl 0266.65008
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.