On the xorshift random number generators

ABSTRACT

G. Marsaglia recently introduced a class of very fast xorshift random number generators, whose implementation uses three “xorshift” operations. They belong to a large family of generators based on linear recurrences modulo 2, which also includes shift-register generators, the Mersenne twister, and several others. In this article, we analyze the theoretical properties of xorshift generators, search for the best ones with respect to the equidistribution criterion, and test them empirically. We find that the vast majority of xorshift generators with only three xorshift operations, including those having good equidistribution, fail several simple statistical tests. We also discuss generators with more than three xorshifts.

REFERENCES

• 1: Brent, R. P. 2004a. Note on Marsaglia's xorshift random number generators. J. Stat. Soft. 11, 5, 1--4. See http://www.jstatsoft.org/v11/i05/brent.pdf.
• 2: Brent, R. P. 2004b. Some uniform and normal random number generators. http://web.comlab.ox.ac.uk/oucl/work/richard.brent/random.html.
• 3: 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]
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: 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]
• 6: L'Ecuyer, P. 2004. Random number generation. In Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, Eds. Springer-Verlag, Berlin, 35--70. Chapter II.2.
• 7: Pierre L'Ecuyer , Jacinthe Granger-Piché, Combined generators with components from different families, Mathematics and Computers in Simulation, v.62 n.3-6, p.395-404, 3 March 2003 [doi>10.1016/S0378-4754(02)00234-3]
• 8: Pierre L'Ecuyer , Richard Simard, Beware of linear congruential generators with multipliers of the form a = ±2q ±2r, ACM Transactions on Mathematical Software (TOMS), v.25 n.3, p.367-374, Sept. 1999 [doi>10.1145/326147.326156]
• 9: Pierre L'Ecuyer , Richard Simard, On the performance of birthday spacings tests with certain families of random number generators, Mathematics and Computers in Simulation, v.55 n.1-3, p.131-137, Feb. 15, 2001 [doi>10.1016/S0378-4754(00)00253-6]
• 10: L'Ecuyer, P. and Simard, R. 2001b. TestU01: A software library in ANSI C for empirical testing of random number generators. Software User's Guide. Available at: http://www.iro.umontreal.ca/~lecuyer.
• 11: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 12: Marsaglia, G. 1985. A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland, Amsterdam, 3--10.
• 13: Marsaglia, G. 2003. Xorshift RNGs. J. Stat. Soft. 8, 14, 1--6. See http://www.jstatsoft.org/v08/i14/xorshift.pdf.
• 14: Jiří Matoušek, On the L2-discrepancy for anchored boxes, Journal of Complexity, v.14 n.4, p.527-556, Dec. 1998 [doi>10.1006/jcom.1998.0489]
• 15: 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]
• 16: 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]
• 17: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 18: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 19: Niederreiter, H. 1995. The multiple-recursive matrix method for pseudorandom number generation. Finite Fields and their Applications 1, 3--30.
• 20: Art B. Owen, Monte Carlo Variance of Scrambled Net Quadrature, SIAM Journal on Numerical Analysis, v.34 n.5, p.1884-1910, Oct. 1997 [doi>10.1137/S0036142994277468]
• 21: Panneton, F. 2004. Construction d'ensembles de points basée sur des récurrences linéaires dans un corps fini de caractéristique 2 pour la simulation Monte Carlo et l'intégration quasi-Monte Carlo. Ph.D. thesis, Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada.
• 22: Panneton, F. and L'Ecuyer, P. 2004. Improved long-period generators based on linear recurrences modulo 2. Manuscript.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
Random number generation, linear feedback shift register, linear recurrence modulo 2, xorshift