Mersenne twister

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (248 KB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 8 , Issue 1 (January 1998) table of contents
Special issue on uniform random number generation

Pages: 3 - 30

Year of Publication: 1998

ISSN:1049-3301

Authors

Makoto Matsumoto	Keio Univ., Yakohama; and the Max-Planch-Institut Für Mathematik, Japan
Takuji Nishimura	Keio Univ., Yokohama, Japan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 71, Downloads (12 Months): 657, Citation Count: 68

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/272991.272995 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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]

CITED BY 68

	Mayur Patel, Random numbers for computer graphics, ACM SIGGRAPH 2006 Sketches, July 30-August 03, 2006, Boston, Massachusetts
	Rudolf Schürer, A comparison between (quasi-)Monte Carlo and cubature rule based methods for solving high-dimensional integration problems, Mathematics and Computers in Simulation, v.62 n.3-6, p.509-517, 3 March 2003
	Hirofumi Wakaki, Edgeworth expansion of Wilks' lambda statistic, Journal of Multivariate Analysis, v.97 n.9, p.1958-1964, October 2006
	Scott Gregory Chastain , Jian Chen, The delivery option in mortgage backed security valuation simulations, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	George Marsaglia, Seeds for random number generators, Communications of the ACM, v.46 n.5, May 2003
	Jurgen A. Doornik, Conversion of high-period random numbers to floating point, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.17 n.1, p.3-es, January 2007
	Shu Tezuka , Hiroki Murata , Shuji Tanaka , Shoji Yumae, Monte Carlo grid for financial risk management, Future Generation Computer Systems, v.21 n.5, p.811-821, May 2005
	Peter Sanders, Presenting data from experiments in algorithmics, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Marco Micocci , Angelo Manna , Alvaro Tomassetti, The comparison of C++ and Mathematica in the generation of pseudo random numbers for financial and actuarial applications, ACM SIGAPL APL Quote Quad, v.29 n.3, p.27-31, March 1999
	Steven F. Railsback , Steven L. Lytinen , Stephen K. Jackson, Agent-based Simulation Platforms: Review and Development Recommendations, Simulation, v.82 n.9, p.609-623, September 2006
	John J. DiLeo, FreeSML: delivering on the open-source simulation language promise, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Pierre L'Ecuyer , Francois Panneton, A new class of linear feedback shift register generators, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	Takuji Nishimura, Tables of 64-bit Mersenne twisters, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.4, p.348-357, Oct. 2000
	Andrew Klapper, Distributional properties of d-FCSR sequences, Journal of Complexity, v.20 n.2-3, p.305-317, April/June 2004
	Tsong Yueh Chen , Fei-Ching Kuo , Robert Merkel, On the statistical properties of testing effectiveness measures, Journal of Systems and Software, v.79 n.5, p.591-601, May 2006
	David M. Nicol, The impact of stochastic variance on worm propagation and detection, Proceedings of the 4th ACM workshop on Recurring malcode, November 03-03, 2006, Alexandria, Virginia, USA
	Shuhei Kimura , Koki Matsumura, Genetic algorithms using low-discrepancy sequences, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Makoto Matsumoto , Takuji Nishimura, Sum-discrepancy test on pseudorandom number generators, Mathematics and Computers in Simulation, v.62 n.3-6, p.431-442, 3 March 2003
	Christopher D. Carothers , Kaylan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.126-135, May 01-04, 1999, Atlanta, Georgia, United States
	Thomas Schell , Stefan Wegenkittl, Looking Beyond Selection Probabilities: Adaptation of the χ² Measure for the Performance Analysis of Selection Methods in GAs, Evolutionary Computation, v.9 n.2, p.243-256, June 2001
	Uri Laserson , Hin Hark Gan , Tamar Schlick, Searching for 2D RNA geometries in bacterial genomes, Proceedings of the twentieth annual symposium on Computational geometry, p.373-377, June 08-11, 2004, Brooklyn, New York, USA
	André Seznec , Nicolas Sendrier, HAVEGE: A user-level software heuristic for generating empirically strong random numbers, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.334-346, October 2003
	Matthew Goode , Korbinian Strimmer , Alexei Drummond , Ed Buckler , Allen Rodrigo, A brief introduction to the Phylogenetic Analysis Library version 1.5, Proceedings of the second conference on Asia-Pacific bioinformatics, p.175-179, January 01, 2004, Dunedin, New Zealand
	Peter Hellekalek , Stefan Wegenkittl, Empirical evidence concerning AES, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.322-333, October 2003
	Antonios Kogias , Dimosthenis Anagnostopoulos, A methodology for the evaluation of web graph models and a test case, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Todd Ebert , Darin Goldstein, A "Go With the Winners" approach to finding frequent patterns, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Christian Bettstetter , Roland Krausser, Scenario-based stability anlysis of the distributed mobility-adaptive clustering (DMAC) algorithm, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
	W. W. Tsang , L. C. K. Hui , K. P. Chow , C. F. Chong , C. W. Tso, Tuning the collision test for power, Proceedings of the 27th Australasian conference on Computer science, p.23-30, January 01, 2004, Dunedin, New Zealand
	Jason M. Daida , Michael E. Samples , Matthew J. Byom, Probing for limits to building block mixing with a tunably-difficult problem for genetic programming, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Kumara Sastry , David E. Goldberg , Xavier Llora, Towards billion-bit optimization via a parallel estimation of distribution algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
	Mark Goresky , Andrew Klapper, Efficient multiply-with-carry random number generators with maximal period, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.310-321, October 2003
	Pierre L'Ecuyer , Renée Touzin, On the Deng-Lin random number generators and related methods, Statistics and Computing, v.14 n.1, p.5-9, January 2004
	B. A. Wichmann , I. D. Hill, Generating good pseudo-random numbers, Computational Statistics & Data Analysis, v.51 n.3, p.1614-1622, December, 2006
	Alejandro L. Garcia , Wolfgang Wagner, Generation of the Maxwellian inflow distribution, Journal of Computational Physics, v.217 n.2, p.693-708, 20 September 2006
	Hande Y. Benson , David F. Shanno, An exact primal---dual penalty method approach to warmstarting interior-point methods for linear programming, Computational Optimization and Applications, v.38 n.3, p.371-399, December 2007
	Pei-Chi Wu, Random number generation with primitive pentanomials, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.4, p.346-351, October 2001
	Krzysztof Pawlikowski , Wolfgang Kreutzer, Tools for teaching simulation: integrating modelling and data analysis in teaching discrete event simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	Kent L. Jones , Thomas N. Wild , David L. Olmsted, Genetic design of discrete dynamical basis networks that approximate data sequences and functions, International Journal of Systems Science, v.35 n.13-14, p.801-814, 20 October 2004
	François Panneton , Pierre L'ecuyer, On the xorshift random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.4, p.346-361, October 2005
	Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland
	Jürgen Branke , Stephen E. Chick , Christian Schmidt, New developments in ranking and selection: an empirical comparison of the three main approaches, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	David B. Thomas , Wayne Luk, High Quality Uniform Random Number Generation Using LUT Optimised State-transition Matrices, Journal of VLSI Signal Processing Systems, v.47 n.1, p.77-92, April 2007
	Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004
	Lih-Yuan Deng , Hongquan Xu, A system of high-dimensional, efficient, long-cycle and portable uniform random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.299-309, October 2003
	Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999
	Jason M. Daida, Towards identifying populations that increase the likelihood of success in genetic programming, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	François Panneton , Pierre L'ecuyer , Makoto Matsumoto, Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.1-16, March 2006
	Vishesh Dhingra , Stéphane Gaubert, How to solve large scale deterministic games with mean payoff by policy iteration, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
	José Ranilla , Oscar Luaces , Antonio Bahamonde, A heuristic for learning decision trees and pruning them into classification rules, AI Communications, v.16 n.2, p.71-87, April 2003
	José Ranilla , Oscar Luaces , Antonio Bahamonde, A heuristic for learning decision trees and pruning them into classification rules, AI Communications, v.16 n.2, p.71-87, 2003
	Catherine McGeoch , Peter Sanders , Rudolf Fleischer , Paul R. Cohen , Doina Precup, Using finite experiments to study asymptotic performance, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Mauricio G. C. Resende , Renato F. Werneck, A Hybrid Heuristic for the p-Median Problem, Journal of Heuristics, v.10 n.1, p.59-88, January 2004
	Vincenzo Liberatore, Caching and Scheduling for Broadcast Disk Systems, Journal of Experimental Algorithmics (JEA), 6, p.5-es, 2001
	Kevin Beyer , Peter J. Haas , Berthold Reinwald , Yannis Sismanis , Rainer Gemulla, On synopses for distinct-value estimation under multiset operations, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Maciej Romaniuk, Pricing the risk-transfer financial instruments via Monte Carlo methods, Systems Analysis Modelling Simulation, v.43 n.8, p.1043-1064, August 2003
	Samuel Kounev , Alejandro Buchmann, SimQPN: a tool and methodology for analyzing queueing Petri net models by means of simulation, Performance Evaluation, v.63 n.4, p.364-394, May 2006
	Jeremy Buhler , Uri Keich , Yanni Sun, Designing seeds for similarity search in genomic DNA, Journal of Computer and System Sciences, v.70 n.3, p.342-363, May 2005
	Walter G. Kropatsch , Yll Haxhimusa , Zygmunt Pizlo , George Langs, Vision pyramids that do not grow too high, Pattern Recognition Letters, v.26 n.3, p.319-337, February 2005
	Shad Stafford , Jun Li , Toby Ehrenkranz, Enhancing SWORD to Detect Zero-Day-Worm-Infected Hosts, Simulation, v.83 n.2, p.199-212, February 2007
	Pierre L'Ecuyer , François Panneton, Fast random number generators based on linear recurrences modulo 2: overview and comparison, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	P. Hellekalek, Don't trust parallel Monte Carlo!, ACM SIGSIM Simulation Digest, v.28 n.1, p.82-89, July 1998
	G. Ginesu , D. D. Giusto , T. Onali, Mutual image-based authentication framework with JPEG2000 in wireless environment, EURASIP Journal on Wireless Communications and Networking, v.2006 n.2, p.76-76, April 2006
	James D. Brown , Gerard B. M. Heuvelink, The Data Uncertainty Engine (DUE): A software tool for assessing and simulating uncertain environmental variables, Computers & Geosciences, v.33 n.2, p.172-190, February, 2007
	Pierre L'Ecuyer, Software for uniform random number generation: distinguishing the good and the bad, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
	Peter Rowat, Interspike Interval Statistics in the Stochastic Hodgkin-Huxley Model: Coexistence of Gamma Frequency Bursts and Highly Irregular Firing, Neural Computation, v.19 n.5, p.1215-1250, May 2007
	Jason M. Daida , Robert R. Bertram , Stephen A. Stanhope , Jonathan C. Khoo , Shahbaz A. Chaudhary , Omer A. Chaudhri , John A. Ii Polito, What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.2, p.165-191, June 2001
	Michael Mascagni , Ashok Srinivasan, Algorithm 806: SPRNG: a scalable library for pseudorandom number generation, ACM Transactions on Mathematical Software (TOMS), v.26 n.3, p.436-461, Sept. 2000
	Pierre L'Ecuyer, Uniform random number generators, Proceedings of the 30th conference on Winter simulation, p.97-104, December 13-16, 1998, Washington, D.C., United States