Makoto Matsumoto
Abstract
A 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-bit accuracy, while using a working area of only 624 words. This is a new variant of the previously proposed generators, TGFSR, modified so as to admit a Mersenne-prime period. The characteristic polynomial has many terms. The distribution up to v bits accuracy for 1 ≤ v ≤ 32 is also shown to be good. An algorithm is also given that checks the primitivity of the characteristic polynomial of MT with computational complexity O(p2) where p is the degree of the polynomial.
We implemented this generator in portable C-code. It passed several stringent statistical tests, including diehard. Its speed is comparable to other modern generators. Its merits are due to the efficient algorithms that are unique to polynomial calculations over the two-element field.
- BRILLHART, J., LEHMER, D. H., SELFRIDGE, J. L., TUCKERMAN, B., AND WAGSTAFF, S. S., JR. 1988. Factorizations of bn _ 1. 2nd ed., Vol. 22, Contemporary Mathematics. AMS, Providence, R.I.Google Scholar
- The hierarchy of correlations in random binary sequences. J. Stat. Phys. 63, 883-896.Google Scholar
- COUTURE, R., L'ECUYER, P., AND TEZUKA, S. 1993. On the distribution of k-dimensional vectors for simple and combined Tausworthe sequences. Math. Comput. 60, 749-761.Google Scholar
- FERRENBERG, A. M., LANDAU, D. P., AND WONG, Y.J. 1992. Monte Carlo simulations: hidden errors from "good" random number generators. Phys. Rev. Lett. 69, 3382-3384.Google ScholarCross Ref
- FREDRICSSON, S.A. 1975. Pseudo-randomness properties of binary shift register sequences. IEEE Trans. Inf. Theor. 21, 115-120.Google ScholarCross Ref
- FUSHIMI, M. 1990. Random number generation with the recursion xt - xt_3p ~ xt_3q. J. Comput. Appl. Math. 31, 105-118. Google ScholarDigital Library
- FUSHIMI, M. AND TEZUKA, S. 1983. The k-distribution of generalized feedback shift register pseudorandom numbers. Commun. ACM 4, 516-523. Google ScholarDigital Library
- HELLEKALEK, P. 1997. Good random number generators are (not so) easy to find. In Proceedings of the Second IMACS Symposium on Mathematical Modeling (Vienna). Google ScholarDigital Library
- HELLEKALEK, P., AUER, T., ENTACHER, K., LEEB, H., LENDL, O., AND WEGENKITTL, S. The PLAB www-server, http://random.mat.sbg.ac.at. Also accessible via ftp.Google Scholar
- HERINGA, J. R., BLOTE, H. W. J., AND COMPAGNER, A. 1992. New primitive trinomials of Mersenne-exponent degrees for random-number generation. Int. J. Modern Phys. C3, 561-564.Google ScholarCross Ref
- KNUTH, D. E. 1981. Seminumerical Algorithms. 2nd ed., Vol. 2, The Art of Computer Programming. Addison Wesley, Reading, MA.Google Scholar
- KNUTH, D.E. 1996. Private communication. Keio Univ., Nov. 1996; Jan. 7th 1997.Google Scholar
- KNUTH, D. E. 1997. Seminumerical Algorithms. 3rd ed., Vol. 2, The Art of Computer Programming. Addison Wesley, Reading, MA. Google ScholarDigital Library
- L'ECUYER, P. 1994. Uniform random number generation. Ann. Oper. Res. 53, 77-120.Google ScholarCross Ref
- L'ECUYER, P. 1996. Maximally equidistributed combined Tausworthe generators. Math. Comput. 65, 203-213. Google ScholarDigital Library
- LENSTRA, A.K. 1985. Factoring multivariate polynomials over finite fields. J. Comput. Syst. Sci. 30, 235-248.Google ScholarCross Ref
- LENSTRA, A. K., LENSTRA, H. W., JR., AND Lovhsz, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 515-534.Google ScholarCross Ref
- LEWIS, T. G. AND PAYNE, W. H. 1973. Generalized feedback shift register pseudorandom number algorithms. J. ACM 20, 456-468. Google ScholarDigital Library
- LINDHOLM, J.H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. Inf. Theor. 14, 569-576.Google ScholarCross Ref
- MARSAGLIA, a. 1985. A current view of random numbers. In Computer Science and Statistics, Proceedings of the Sixteenth Symposium on The Interface, North-Holland, Amsterdam, 3-10.Google Scholar
- MARSAGLIA, G. AND ZAMAN, A. 1991. A new class of random number generators. Ann. Appl. Probab. 1, 462-480.Google ScholarCross Ref
- MATSUMOTO, M. AND KURITA, Y. 1992. Twisted GFSR generators. ACM Trans. Model. Comput. Simul. 2, 179-194. Google ScholarDigital Library
- MATSUMOTO, M. AND KURITA, Y. 1994. Twisted GFSR generators II. ACM Trans. Model. Comput. Simul. 4, 254-266. Google ScholarDigital Library
- MATSUMOTO, M. AND KURITA, Y. 1996. Strong deviations from randomness in m-sequences based on trinomials. ACM Trans. Model. Comput. Simul. 6, 99-106. Google ScholarDigital Library
- NIEDERREITER, H. 1993. Factorization of polynomials and some linear-algebra problems over finite fields. Linear Algebra Appl. 192, 301-328.Google ScholarCross Ref
- NIEDERREITER, H. 1995. The multiple-recursive matrix method for pseudorandom number generation. Finite Fields Appl. 1, 3-30. Google ScholarDigital Library
- RUEPPEL, R.A. 1986. Analysis and Design of Stream Ciphers. Communication and Control Engineering Series. Springer-Verlag, New York, NY. Google ScholarDigital Library
- TEZUKA, S. 1990. Lattice structure of pseudorandom sequences from shift register generators. In Proceedings of the 1990 Winter Simulation Conference R. E. Nance Ed. IEEE, 266 -269. Google ScholarDigital Library
- TEZUKA, S. 1994a. The k-dimensional distribution of combined GFSR sequences. Math. Comput. 62, 809-817. Google ScholarDigital Library
- TEZUKA, S. 1994b. A unified view of long-period random number generators. J. Oper. Res. Soc. Japan 37, 211-227.Google Scholar
- TEZUKA, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer.Google Scholar
- TEZUKA, S. AND L'ECUYER, P. 1991. Efficient and portable combined Tausworthe random number generators. ACM Trans. Model. Comput. Simul. 1, 99-112. Google ScholarDigital Library
- TEZUKA, S., L'ECUYER, P., AND COUTURE, R. 1993. On the lattice structure of the add-withcarry and subtract-with-borrow random number generators. ACM Trans. Model. Comput. Simul. 3, 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, 3, 469-481. Google ScholarDigital Library
Index Terms
- Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Recommendations
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 ...
Twisted GFSR generators II
The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property. We ...
Comments