Shin Harase
Skip Abstract Section
Skip Supplemental Material SectionAbstract
CPUs and operating systems are moving from 32 to 64 bits, and hence it is important to have good pseudorandom number generators designed to fully exploit these word lengths. However, existing 64-bit very long period generators based on linear recurrences modulo 2 are not completely optimized in terms of the equidistribution properties. Here, we develop 64-bit maximally equidistributed pseudorandom number generators that are optimal in this respect and have speeds equivalent to 64-bit Mersenne Twisters. We provide a table of specific parameters with period lengths from 2607-1 to 244497-1.
Supplemental Material
Available for Download
zip
harase.zip (95.2 KB)
Supplemental movie, appendix, image and software files for, Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period
- A. Compagner. 1991. The hierarchy of correlations in random binary sequences. Journal of Statistical Physics 63 (1991), 883--896. Issue 5.Google Scholar
Cross Ref
- R. Couture and P. L’Ecuyer. 2000. Lattice computations for random numbers. Mathematics of Computation 69, 230 (2000), 757--765. Google ScholarDigital Library
- H. Haramoto, M. Matsumoto, T. Nishimura, F. Panneton, and P. L’Ecuyer. 2008. Efficient jump ahead for -linear random number generators. INFORMS Journal of Computing 20, 3 (2008), 385--390. Google ScholarDigital Library
- S. Harase. 2009. Maximally equidistributed pseudorandom number generators via linear output transformations. Mathematics and Computers in Simulation 79, 5 (2009), 1512--1519. Google ScholarDigital Library
- S. Harase. 2011. An efficient lattice reduction method for -linear pseudorandom number generators using Mulders and Storjohann algorithm. Journal of Computation and Applied Mathematics 236, 2 (2011), 141--149.Google ScholarCross Ref
- S. Harase, M. Matsumoto, and M. Saito. 2011. Fast lattice reduction for -linear pseudorandom number generators. Mathematics of Computation 80, 273 (2011), 395--407.Google ScholarCross Ref
- ISO. 2012. ISO/IEC 14882:2011 Information Technology — Programming Languages — C++. International Organization for Standardization, Geneva, Switzerland. 1338 (est.) pages.Google Scholar
- D. E. Knuth. 1997. The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA. Google ScholarDigital Library
- P. L’Ecuyer. 1999. Tables of maximally equidistributed combined LFSR generators. Mathematics of Computation 68, 225 (1999), 261--269. Google ScholarDigital Library
- P. L’Ecuyer and F. Panneton. 2009. -Linear Random Number Generators. In Advancing the Frontiers of Simulation: A Festschrift in Honor of George Samuel Fishman, C. Alexopoulos, D. Goldsman, and J. R. Wilson (Eds.). Springer-Verlag, New York, 169--193.Google Scholar
- P. L’Ecuyer and R. Simard. 2007. TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematics Software 33, 4 (2007), Art. 22, 40. Google ScholarDigital Library
- J. H. Lindholm. 1968. An analysis of the pseudo-randomness properties of subsequences of long -sequences. IEEE Transactions on Information Theory IT-14, 4 (1968), 569--576. Google ScholarDigital Library
- M. Matsumoto and Y. Kurita. 1996. Strong deviations from randomness in -sequences based on trinomials. ACM Transactions on Modeling and Computer Simulation 6, 2 (Apr 1996), 99--106. Google ScholarDigital Library
- M. Matsumoto and T. Nishimura. 1998. Mersenne twister: A -dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8, 1 (1998), 3--30. Google ScholarDigital Library
- M. Matsumoto and T. Nishimura. 2002. A nonempirical test on the weight of pseudorandom number generators. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K.-T. Fang, F. J. Hickernell, and H. Niederreiter (Eds.). Springer, Berlin, 381--395.Google Scholar
- M. Matsumoto, M. Saito, H. Haramoto, and T. Nishimura. 2006. Pseudorandom number generation: Impossibility and compromise. Journal of Universal Computer Science 12, 6 (2006), 672--690.Google Scholar
- M. Matsumoto, I. Wada, A. Kuramoto, and H. Ashihara. 2007. Common defects in initialization of pseudorandom number generators. ACM Transactions on Modeling and Computer Simulation 17, 4, Article 15 (Sep 2007). Google ScholarDigital Library
- H. Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Reginal Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia. Google ScholarDigital Library
- T. Nishimura. 2000. Tables of 64-bit Mersenne twister. ACM Transactions on Modeling and Computer Simulation 10, 4 (2000), 348--357. Google ScholarDigital Library
- F. Panneton, P. L’Ecuyer, and M. Matsumoto. 2006. Improved long-period generators based on linear recurrences modulo 2. ACM Transactions on Mathematical Software 32, 1 (2006), 1--16. Google ScholarDigital Library
- M. Saito and M. Matsumoto. 2008. SIMD-oriented fast Mersenne twister: A 128-bit pseudorandom number generator. In Monte Carlo and Quasi-Monte Carlo Methods 2006, A. Keller, S. Heinrich, and H. Niederreiter (Eds.). Springer-Verlag, Berlin, 607--622.Google Scholar
- M. Saito and M. Matsumoto. 2009. A PRNG specialized in double precision floating point numbers using an affine transition. In Monte Carlo and Quasi-Monte Carlo Methods 2008, P. L’Ecuyer and A. B. Owen (Eds.). Springer, Berlin, 589--602.Google Scholar
- M. Saito and M. Matsumoto. 2013. Variants of Mersenne twister suitable for graphic processors. ACM Transactions on Mathematical Software 39, 2 (2013), Art. 12, 20. Google ScholarDigital Library
- J. P. R. Tootill, W. D. Robinson, and D. J. Eagle. 1973. An asymptotically random Tausworthe sequence. Journal of the ACM 20, 3 (1973), 469--481. Google ScholarDigital Library
- D. K. Wang and A. Compagner. 1993. On the use of reducible polynomials as random number generators. Mathematics of Computation 60, 201 (1993), 363--374. 0025-5718Google ScholarCross Ref
Index Terms
- Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period
Recommendations
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Special issue on uniform random number generationA new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 219937 −1 and 623-dimensional equidistribution up to 32-...
Tables of 64-bit Mersenne twisters
We give new parameters for a Mersenne Twister pseudorandom number gene rator for 64-bit word machines.
Improved long-period generators based on linear recurrences modulo 2
Fast uniform random number generators with extremely long periods have been defined and implemented based on linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the period length, the statistical ...
Comments