Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator

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.

REFERENCES

• 1: 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.
• 2: The hierarchy of correlations in random binary sequences. J. Stat. Phys. 63, 883-896.
• 3: 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.
• 4: 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.
• 5: FREDRICSSON, S.A. 1975. Pseudo-randomness properties of binary shift register sequences. IEEE Trans. Inf. Theor. 21, 115-120.
• 6: M. Fushimi, Random number generation with the recursion Xt=Xt-3p⊕Xt-3q , Journal of Computational and Applied Mathematics, v.31 n.1, p.105-118, July 1990 [doi>10.1016/0377-0427(90)90341-V]
• 7: M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983 [doi>10.1145/358150.358159]
• 8: P. Hellekalek, Good random number generators are (not so) easy to find, Selected papers from the 2nd IMACS symposium on Mathematical modelling---2nd MATHMOD, p.485-505, June 1998, Vienna, Austria
• 9: 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.
• 10: 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.
• 11: KNUTH, D. E. 1981. Seminumerical Algorithms. 2nd ed., Vol. 2, The Art of Computer Programming. Addison Wesley, Reading, MA.
• 12: KNUTH, D.E. 1996. Private communication. Keio Univ., Nov. 1996; Jan. 7th 1997.
• 13: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: L'ECUYER, P. 1994. Uniform random number generation. Ann. Oper. Res. 53, 77-120.
• 15: Pierre L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation, v.65 n.213, p.203-213, Jan. 1996 [doi>10.1090/S0025-5718-96-00696-5]
• 16: LENSTRA, A.K. 1985. Factoring multivariate polynomials over finite fields. J. Comput. Syst. Sci. 30, 235-248.
• 17: LENSTRA, A. K., LENSTRA, H. W., JR., AND Lovhsz, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 515-534.
• 18: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 19: LINDHOLM, J.H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. Inf. Theor. 14, 569-576.
• 20: 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.
• 21: MARSAGLIA, G. AND ZAMAN, A. 1991. A new class of random number generators. Ann. Appl. Probab. 1, 462-480.
• 22: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.179-194, July 1992 [doi>10.1145/146382.146383]
• 23: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators II, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.254-266, July 1994 [doi>10.1145/189443.189445]
• 24: Makoto Matsumoto , Yoshiharu Kurita, Strong deviations from randomness in m-sequences based on trinomials, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.2, p.99-106, April 1996 [doi>10.1145/232807.232815]
• 25: NIEDERREITER, H. 1993. Factorization of polynomials and some linear-algebra problems over finite fields. Linear Algebra Appl. 192, 301-328.
• 26: NIEDERREITER, H. 1995. The multiple-recursive matrix method for pseudorandom number generation. Finite Fields Appl. 1, 3-30.
• 27: Rainer A. Rueppel, Analysis and design of stream ciphers, Springer-Verlag New York, Inc., New York, NY, 1986
• 28: Shu Tezuka, Lattice structure of pseudorandom sequences from shift-register generators, Proceedings of the 22nd conference on Winter simulation, p.266-269, December 09-12, 1990, New Orleans, Louisiana, United States
• 29: Shu Tezuka, The k-dimensional distribution of combined GFSR sequences, Mathematics of Computation, v.62 n.206, p.809-817, April 1994 [doi>10.2307/2153541]
• 30: TEZUKA, S. 1994b. A unified view of long-period random number generators. J. Oper. Res. Soc. Japan 37, 211-227.
• 31: TEZUKA, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer.
• 32: Shu Tezuka , Pierre L'Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.2, p.99-112, April 1991 [doi>10.1145/116890.116892]
• 33: Shu Tezuka , Pierre L'Ecuyer , Raymond Couture, On the lattice structure of the add-with-carry and subtract-with-borrow random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.4, p.315-331, Oct. 1993 [doi>10.1145/159737.159749]
• 34: J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Recurrences and difference equations

General Terms:
Algorithms, Experimentation, Theory

Keywords:
k-distribution, m-sequences, GFSR, MT19937, Mersenne primes, Mersenne twister, TGFSR, finite fields, incomplete array, inversive-decimation method, multiple-recursive matrix method, primitive polynomials, random number generation, tempering