The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
An Experimental Exploration of Marsaglia's xorshift Generators, Scrambled
Open accessAbstract
Marsaglia proposed xorshift generators are a class of very fast, good-quality pseudorandom number generators. Subsequent analysis by Panneton and L'Ecuyer has lowered the expectations raised by Marsaglia's article, showing several weaknesses of such generators. Nonetheless, many of the weaknesses of xorshift generators fade away if their result is scrambled by a nonlinear operation (as originally suggested by Marsaglia). In this article we explore the space of possible generators obtained by multiplying the result of a xorshift generator by a suitable constant. We sample generators at 100 points of their state space and obtain detailed statistics that lead us to choices of parameters that improve on the current ones. We then explore for the first time the space of high-dimensional xorshift generators, following another suggestion in Marsaglia's article, finding choices of parameters providing periods of length 2 1024 − 1 and 2 4096 − 1. The resulting generators are of extremely high quality, faster than current similar alternatives, and generate long-period sequences passing strong statistical tests using only eight logical operations, one addition, and one multiplication by a constant.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Numerical recipes in C: the art of scientific computing
(1993) · Choice Reviews Online · doi:10.5860/choice.30-5638 · Cited by 17,933
Numerical Recipes, The Art of Scientific Computing
Press, W. H., Flannery, B. P., Teukolsky, S. A., Vetterling, W. T., & Gould, H. (1987) · American Journal of Physics · doi:10.1119/1.14981 · Cited by 10,024
A NEW MEASURE OF RANK CORRELATION
KENDALL, M. G. (1938) · Biometrika · doi:10.1093/biomet/30.1-2.81 · Cited by 7,269 · cited 1×
“The scatter plot in Figure 5 and Kendall’s(5) τ ≈ 0.98 between the two rankings we obtain make rather clear that this is not the case. In particular, the four best conjugate pairs in Table I are the same with both seeds. To gather more information, we ran the full BigCrush suite and Dieharder on our four best generato…”
InfluentialMersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780 · cited 1×
“2 1). 9. COMPARISON How do our best xorshift* generators score with respect to more complex generators in the literature? We decided to perform a comparison with the popular Mersenne Twister MT19937 [Matsumoto and Nishimura 1998],13 with WELL1024a/WELL19937a, two generators introduced by Panneton et al. [2006] as an i…”
ResultBassham, L. E., Rukhin, A. L., Soto, J., Nechvatal, J. R., Smid, M. E., Barker, E. B., Leigh, S. D., Levenson, M., Vangel, M., Banks, D. L., et al. (2010) · NIST Special Publication 800-22 Revision 1a · doi:10.6028/nist.sp.800-22r1a · Cited by 3,617 · cited 1×
“Indeed, other, more sophisticated methods might be used to aggreate the result of our samples: combining p-values, for instance, or computing a p-value of p-values [Rukhin et al. 2001].”
MethodRandom Number Generation and Quasi-Monte Carlo Methods.
Collings, B. J., & Niederreiter, H. (1993) · Journal of the American Statistical Association · doi:10.2307/2290359 · Cited by 2,884
Introduction to Finite Fields and their Applications
Lidl, R., & Niederreiter, H. (1994) · Cambridge University Press eBooks · doi:10.1017/cbo9781139172769 · Cited by 2,069
Rukhin, A., Sota, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., et al. (2000) · doi:10.6028/nist.sp.800-22 · Cited by 1,867
TestU01: A C library for empirical testing of random number generators
L'Ecuyer, P., & Simard, R. (2007) · ACM Transactions on Mathematical Software · doi:10.1145/1268776.1268777 · Cited by 1,014
THE TREATMENT OF TIES IN RANKING PROBLEMS
KENDALL, M. G. (1945) · Biometrika · doi:10.1093/biomet/33.3.239 · Cited by 809 · cited 1×
“The first and most important is TestU01, a test suite developed by L’Ecuyer and Simard [2007] that contains several tests oriented towards the generation of uniform real numbers in [0 .”
BackgroundMarsaglia, G. (2003) · Journal of Statistical Software · doi:10.18637/jss.v008.i14 · Cited by 434 · cited 1×
“HIGH DIMENSION Marsaglia [2003] describes a strategy for xorshift generators in high dimension: the idea is to use always three low-dimensional shifts, but locating them in the context of a larger matrix of the form”
BackgroundThe Treatment of Ties in Ranking Problems
Kendall, M. G. (1945) · Biometrika · doi:10.2307/2332303 · Cited by 391
Improved long-period generators based on linear recurrences modulo 2
Panneton, F., L'Ecuyer, P., & Matsumoto, M. (2006) · ACM Transactions on Mathematical Software · doi:10.1145/1132973.1132974 · Cited by 283 · cited 6×
“Moreover, equidistribution is currently impossible to evaluate exactly for long-period non-linear generators, and it is known to be biased towards the high bits [L’Ecuyer and Panneton 2005]: for instance, the WELL1024a generator has been designed to be maximally equidistributed [Panneton et al. 2006], and indeed it ha…”
BackgroundResultInfluentialSIMD-Oriented Fast Mersenne Twister: a 128-bit Pseudorandom Number Generator
Saito, M., & Matsumoto, M. (2008) · Monte Carlo and Quasi-Monte Carlo Methods 2006 · doi:10.1007/978-3-540-74496-2_36 · Cited by 257 · cited 1×
“ults are shown in Table XIII (variance is undetectable, as we generate 1010 values in each test). We also report as a strong baseline results about SFMT19937, the SIMD-Oriented Fast Mersenne Twister [Saito and Matsumoto 2008], a 128-bit version of the Mersenne Twister based on the SSE2 extended instruction set of Inte…”
Tables of linear congruential generators of different sizes and good lattice structure
L’Ecuyer, P. (1999) · Mathematics of Computation · doi:10.1090/s0025-5718-99-00996-5 · Cited by 232
Monte Carlo and Quasi-Monte Carlo Methods 2004
(2006) · Springer eBooks · doi:10.1007/3-540-31186-6 · Cited by 198
Matrices and the structure of random number sequences
Marsaglia, G., & Tsay, L.-H. (1985) · Linear Algebra and its Applications · doi:10.1016/0024-3795(85)90192-2 · Cited by 118 · cited 1×
“tructure taken by powers of the linear transformation Massociated with a generator to compute such powers explicitly, and store them using space linear in the size of the state space: as it is known [Marsaglia and Tsay 1985], the generator has full period if and only if Mhas the same multiplicative period. It is thus…”
MethodOn the xorshift random number generators
Panneton, F., & L’Ecuyer, P. (2005) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/1113316.1113319 · Cited by 104
Some long-period random number generators using shifts and xors
Brent, R. P. (2007) · ANZIAM Journal · doi:10.21914/anziamj.v48i0.40 · Cited by 58
Note on Marsaglia's Xorshift Random Number Generators
Brent, R. P. (2004) · Journal of Statistical Software · doi:10.18637/jss.v011.i05 · Cited by 51
Uniform Random Number Generators for Supercomputers
Brent, R. P. (1992) · ANU Open Research (Australian National University) · Cited by 50
The hierarchy of correlations in random binary sequences
Compagner, A. (1991) · Journal of Statistical Physics · doi:10.1007/bf01029989 · Cited by 48 · cited 2×
“It is considered a good property for generators of this kind that the weight is close to n/2, that is, that the polynomial is neither too sparse nor too dense [Compagner 1991]. Note that the family of algorithms of Figure 1 is intended to generate 64-bit values. This means that the entire output of the algorithm shoul…”
Combined generators with components from different families
L’Ecuyer, P., & Granger-Piché, J. (2003) · Mathematics and Computers in Simulation · doi:10.1016/s0378-4754(02)00234-3 · Cited by 38
Fast random number generators based on linear recurrences modulo 2: overview and comparison
L’Ecuyer, P., & Panneton, F. (2005) · Winter Simulation Conference · doi:10.5555/1162708.1162732 · Cited by 34
Panneton, F. (2004) · Papyrus : Institutional Repository (Université de Montréal) · doi:10.71781/10219 · Cited by 16
Harase, S. (2011) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2011.06.005 · Cited by 7 · cited 6×
“We computed the equidistribution score for all generators using the implementation of Harase’s algorithm [Harase 2011] contained in the MTToolBox package from Saito [2013]. Similarly to SmallCrush scores, 1 has highbits bias and a quite strong one [L’Ecuyer and Panneton 2005].”
MethodInfluentialThe myth of equidistribution for high-dimensional simulationPreprint
Brent, R. P. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.1320 · Cited by 4
Research works printed but not linked: 3
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics (2nd ed.). Addison--Wesley.
- Robert H. Lewis. 2013. Fermat: A Computer Algebra System for Polynomial and Matrix Computation (Version 5.1). (2013). Retrieved January 8, 2014 from http://home.bway.net/lewis/.
- 10.5555/130653 · doi:10.5555/130653
Cited by
The Belle II Core Software: Belle II Framework Software Group
Kuhr, T., Pulvermacher, C., Ritter, M., Hauth, T., & Braun, N. (2019) · Computing and Software for Big Science · doi:10.1007/s41781-018-0017-9 · Cited by 204
“For Belle II, we chose xorshift1024* [28], a newer generation PRNG based on the Xorshift algorithm proposed by Marsaglia [29].”
MethodScrambled Linear Pseudorandom Number Generators
Blackman, D., & Vigna, S. (2021) · ACM Transactions on Mathematical Software · doi:10.1145/3460772 · Cited by 177
“, see Theorem 14 of [7], which can be used to prove (3) for xorshift linear engines with multiple-word state [39]).”
InfluentialSelf-citationA search for good pseudo-random number generators: Survey and empirical studies
Bhattacharjee, K., & Das, S. K. (2022) · Computer Science Review · doi:10.1016/j.cosrev.2022.100471 · Cited by 173
“Whereas, in [17], to remove the flaws of xorshift generators, a non-linear operation is applied to scramble the results.”
BackgroundMethodFIREbox: simulating galaxies at high dynamic range in a cosmological volume
Feldmann, R., Quataert, E., Faucher‐Giguère, C., Hopkins, P. F., Çatmabacak, O., Kereš, D., Bassini, L., Bernardini, M., Bullock, J. S., Cenci, E., et al. (2023) · Monthly Notices of the Royal Astronomical Society · doi:10.1093/mnras/stad1205 · Cited by 182
A Guideline on Pseudorandom Number Generation (PRNG) in the IoT
Kietzmann, P., Schmidt, T. C., & Wählisch, M. (2021) · ACM Computing Surveys · doi:10.1145/3453159 · Cited by 128
“owing. Marsaglia [82] proposed a collection of extended Xorshift PRNGs with an increased period length and improved statistical properties. Vigna et al. analyzed and improved these generators further [83]–[85]. We briefly discuss results about the Xorshift64* and the Xoroshiro128+ derivatives at the side, which we inte…”
Background
Metadata
- Authors
- Vigna, S.
- Affiliations
- University of Milan (IT)
- Corresponding author
- Vigna, Sebastiano
- ORCID
- Vigna, Sebastiano
- Venue
- ACM Transactions on Mathematical Software
- Published
- 2016-06-14
- Volume
- 42
- Issue
- 4
- Pages
- 1-23
- ISSN
- 0098-3500 (ISSN-L)
- 1557-7295
- OpenAlex
- W1768180846
- Cited by
- 55
- References
- 25
- Citations by year
- 2026: 5 · 2025: 7 · 2024: 2 · 2023: 3 · 2022: 5 · 2021: 8 · 2020: 1 · 2019: 9 · 2018: 6 · 2017: 2 · 2016: 4
- FWCI
- 7.47
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- ACM Transactions on Mathematical Software (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- EU-FET (NADINE (GA 288956))
- Topics
- Physical Sciences › Mathematics › Numerical Analysis › Mathematical Approximation and Integration
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Numerical Methods and Algorithms
- Physical Sciences › Mathematics › Modeling and Simulation › Mathematical and Computational Methods
- Keywords
- pseudorandom number generators, scrambling, long period, randomness testing, linear feedback shift registers
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.