article

On the xorshift random number generators

Authors:

François Panneton,

Pierre L'EcuyerAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 15, Issue 4

Pages 346 - 361

https://doi.org/10.1145/1113316.1113319

Published: 01 October 2005 Publication History

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]

Fushimi, M. and Tezuka, S. 1983. The k-distribution of generalized feedback shift register pseudorandom numbers. Comm. ACM 26, 7, 516--523.

[4]

Knuth, D. E. 1998. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third ed. Addison-Wesley, Reading, Mass.

[5]

L'Ecuyer, P. 1996. Maximally equidistributed combined Tausworthe generators. Mathematics of Computation 65, 213, 203--213.

[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]

L'Ecuyer, P. and Granger-Piché, J. 2003. Combined generators with components from different families. Mathematics and Computers in Simulation 62, 395--404.

[8]

L'Ecuyer, P. and Simard, R. 1999. Beware of linear congruential generators with multipliers of the form a = ± 2q ± 2r. ACM Trans. Math. Soft. 25, 3, 367--374.

[9]

L'Ecuyer, P. and Simard, R. 2001a. On the performance of birthday spacings tests for certain families of random number generators. Mathematics and Computers in Simulation 55, 1--3, 131--137.

[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]

Lidl, R. and Niederreiter, H. 1994. Introduction to Finite Fields and Their Applications, Revised Ed. Cambridge University Press, Cambridge.

[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]

Matousěk, J. 1998. On the L2-discrepancy for anchored boxes. J. Complexity 14, 527--556.

[15]

Matsumoto, M. and Kurita, Y. 1992. Twisted GFSR generators. ACM Trans. Model. Comput. Simul. 2, 3, 179--194.

[16]

Matsumoto, M. and Kurita, Y. 1994. Twisted GFSR generators II. ACM Trans. Model. Comput. Simul. 4, 3, 254--266.

[17]

Matsumoto, M. and Nishimura, T. 1998. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 1, 3--30.

[18]

Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia.

[19]

Niederreiter, H. 1995. The multiple-recursive matrix method for pseudorandom number generation. Finite Fields and their Applications 1, 3--30.

[20]

Owen, A. B. 1997. Monte Carlo variance of scrambled equidistribution quadrature. SIAM J. Numer. Anal. 34, 5, 1884--1910.

[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.

Cited By

Ding ZHe DQiao QLi XGao YChan SChoo K(2024)A Lightweight and Secure Communication Protocol for the IoT EnvironmentIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.326797921:3(1050-1067)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3267979
Meleshenko PSemenov MKanishcheva O(2024)A Novel Pseudorandom Number Generator Based on the Conservative Chaotic System with Non-smooth NonlinearitiesAdvances in Nonlinear Dynamics and Control of Mechanical and Physical Systems10.1007/978-981-99-7958-5_18(219-236)Online publication date: 27-Feb-2024
https://doi.org/10.1007/978-981-99-7958-5_18
Wen XZhu RHe ZHuang SYin ZLiu GLiu ZMa Q(2023)A Linear Recurrence-Based Pseudorandom Number Generator Optimized for Detector EmulatorsIEEE Transactions on Nuclear Science10.1109/TNS.2023.328525170:8(2139-2147)Online publication date: Aug-2023
https://doi.org/10.1109/TNS.2023.3285251
Show More Cited By

Index Terms

On the xorshift random number generators
1. Computing methodologies
  1. Modeling and simulation
2. Mathematics of computing
  1. Mathematical software

Recommendations

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 ...
Resolution-stationary random number generators

Besides speed and period length, the quality of uniform random number generators (RNGs) is usually assessed by measuring the uniformity of their point sets, formed by taking vectors of successive output values over their entire period length. For F"2-...
Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 15, Issue 4

October 2005

97 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/1113316

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005

Published in TOMACS Volume 15, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
1,136
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding ZHe DQiao QLi XGao YChan SChoo K(2024)A Lightweight and Secure Communication Protocol for the IoT EnvironmentIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.326797921:3(1050-1067)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3267979
Meleshenko PSemenov MKanishcheva O(2024)A Novel Pseudorandom Number Generator Based on the Conservative Chaotic System with Non-smooth NonlinearitiesAdvances in Nonlinear Dynamics and Control of Mechanical and Physical Systems10.1007/978-981-99-7958-5_18(219-236)Online publication date: 27-Feb-2024
https://doi.org/10.1007/978-981-99-7958-5_18
Wen XZhu RHe ZHuang SYin ZLiu GLiu ZMa Q(2023)A Linear Recurrence-Based Pseudorandom Number Generator Optimized for Detector EmulatorsIEEE Transactions on Nuclear Science10.1109/TNS.2023.328525170:8(2139-2147)Online publication date: Aug-2023
https://doi.org/10.1109/TNS.2023.3285251
Sandakly SSalem CChallita KDass SAzar JAbdo JDemerjian J(2023)XorshiftH128+: A hybrid random number generator for lightweight IoT2023 IEEE International Conference on Artificial Intelligence, Blockchain, and Internet of Things (AIBThings)10.1109/AIBThings58340.2023.10292458(1-5)Online publication date: 16-Sep-2023
https://doi.org/10.1109/AIBThings58340.2023.10292458
Zhu DLin YSun GWang FZhao MChen YDuan J(2023)Critical Ising system testing of high-quality random number generatorsJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ace0b72023:7(073203)Online publication date: 18-Jul-2023
https://doi.org/10.1088/1742-5468/ace0b7
Noura HSalman OCouturier RChehab A(2023)LESCA: LightwEight Stream Cipher Algorithm for emerging systemsAd Hoc Networks10.1016/j.adhoc.2022.102999138(102999)Online publication date: Jan-2023
https://doi.org/10.1016/j.adhoc.2022.102999
Noura HSalman OCouturier RChehab A(2022)LoRCAVehicular Communications10.1016/j.vehcom.2021.10041634:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.vehcom.2021.100416
Seyhan KAkleylek S(2022)Classification of random number generator applications in IoT: A comprehensive taxonomyJournal of Information Security and Applications10.1016/j.jisa.2022.10336571(103365)Online publication date: Dec-2022
https://doi.org/10.1016/j.jisa.2022.103365
Bhattacharjee KDas S(2022)A search for good pseudo-random number generatorsComputer Science Review10.1016/j.cosrev.2022.10047145:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.cosrev.2022.100471
Haramoto HMatsumoto MSaito M(2022)Unveiling patterns in xorshift128+ pseudorandom number generatorsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113791402:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.cam.2021.113791
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents