View source for Xorshift

{{short description|Class of pseudorandom number generators}}
[[File:Xorshift.png|thumb|right|Example random distribution of Xorshift128]]
'''Xorshift''' random number generators, also called '''shift-register generators''', are a class of [[Pseudorandom number generator|pseudorandom number generator]]s that were invented by [[Biography:George Marsaglia|George Marsaglia]].<ref name="marsaglia" /> They are a subset of [[Linear-feedback shift register|linear-feedback shift register]]s (LFSRs) which allow a particularly efficient implementation in software without the excessive use of [[Sparse polynomial|sparse polynomial]]s.<ref name="brent" /> They generate the next number in their sequence by repeatedly taking the [[Bitwise operation#XOR|exclusive or]] of a number with a [[Logical shift|bit-shifted]] version of itself. This makes execution extremely efficient on modern computer architectures, but it does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.<ref name="panne" />

For execution in software, xorshift generators are among the fastest PRNGs, requiring very small code and state. However, they do not pass every statistical test without further refinement. This weakness is amended by combining them with a non-linear function, as described in the original paper. Because plain xorshift generators (without a non-linear step) fail some statistical tests, they have been accused of being unreliable.{{r|panne|p=360}}

==Example implementation==
A [[C (programming language)|C]] version{{efn|In C and most other C-based languages, {{code|^}} represents [[Bitwise operation#XOR|bitwise XOR]], and {{code|<<}} and {{code|>>}} represent [[Logical shift|bitwise shift]]s.}} of three xorshift algorithms{{r|marsaglia|p=4,5}} is given here. The first has one 32-bit word of state, and period 2<sup>32</sup>−1. The second has one 64-bit word of state and period 2<sup>64</sup>−1. The last one has four 32-bit words of state, and period 2<sup>128</sup>−1. The 128-bit algorithm passes the [[Diehard tests|diehard tests]]. However, it fails the ''MatrixRank'' and ''LinearComp'' tests of the ''BigCrush'' test suite from the [[TestU01]] framework.

All use three shifts and three or four exclusive-or operations:
<!-- "unsigned long" and "unsigned long long" in the original paper changed to explicit sized types from <stdint.h> -->
<source lang="c">
#include <stdint.h>

struct xorshift32_state {
    uint32_t a;
};

/* The state must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
    uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

/* struct xorshift128_state can alternatively be defined as a pair
   of uint64_t or a uint128_t where supported */
struct xorshift128_state {
    uint32_t x[4];
};

/* The state must be initialized to non-zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t  = state->x[3];
    
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
	state->x[3] = state->x[2];
	state->x[2] = state->x[1];
	state->x[1] = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->x[0] = t ^ s ^ (s >> 19);
}
</source>

==Non-linear variations==
All xorshift generators fail some tests in the ''BigCrush'' test suite. This is true for all generators based on linear recurrences, such as the [[Mersenne Twister]] or WELL. However, it is easy to scramble the output of such generators to improve their quality.

The scramblers known as {{mono|+}} and {{mono|*}} still leave weakness in the low bits,<ref name=Lemire19/> so they are intended for floating point use, as double-precision floating-point numbers only use 53 bits, so the lower 11 bits are not used. For general purpose, the scrambler {{mono|**}} (pronounced ''starstar'') makes the LFSR generators pass in all bits.

===xorwow===
Marsaglia suggested scrambling the output by combining it with a simple additive counter modulo 2<sup>32</sup> (which he calls a "[[Weyl sequence]]" after Weyl's equidistribution theorem). This also increases the period by a factor of 2<sup>32</sup>, to 2<sup>192</sup>−2<sup>32</sup>:
<source lang="c">
#include <stdint.h>

struct xorwow_state {
    uint32_t x[5];
    uint32_t counter;
};

/* The state array must be initialized to not be all zero in the first four words */
uint32_t xorwow(struct xorwow_state *state)
{
    /* Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs" */
    uint32_t t  = state->x[4];
 
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
    state->x[4] = state->x[3];
    state->x[3] = state->x[2];
    state->x[2] = state->x[1];
    state->x[1] = s;
 
    t ^= t >> 2;
    t ^= t << 1;
    t ^= s ^ (s << 4);
    state->x[0] = t;
    state->counter += 362437;
    return t + state->counter;
}
</source>
This performs well, but fails a few tests in BigCrush.<ref>{{cite web
 |title=XORWOW L'ecuyer TestU01 Results
 |url=https://chasethedevil.github.io/post/xorwow-lecuyer-testu01-results/
 |date=12 January 2011
 |website=Chase The Devil (blog)
 |first=Fabien |last=Le Floc'h
 |access-date=2017-11-02
}}</ref>  This generator is the default in Nvidia's [[Software:CUDA|CUDA]] toolkit.<ref>{{cite web
 |url=https://docs.nvidia.com/cuda/curand/testing.html
 |title=cuRAND Testing
 |publisher=[[Company:Nvidia|Nvidia]]
 |access-date=2017-11-02
}}</ref>

===xorshift*===
An {{em|xorshift*}} generator applies an invertible multiplication (modulo the word size) as a non-linear transformation to the output of an {{em|xorshift}} generator, as suggested by Marsaglia.<ref name="marsaglia"/> All {{em|xorshift*}} generators emit a sequence of values that is equidistributed in the maximum possible dimension (except that they will never output zero for 16 calls, i.e. 128 bytes, in a row).<ref name="vigna"/>

The following 64-bit generator has a maximal period of 2<sup>64</sup>−1.<ref name="vigna" />
<source lang="c">
#include <stdint.h>

/* xorshift64s, variant A_1(12,25,27) with multiplier M_32 from line 3 of table 5 */
uint64_t xorshift64star(void) {
    /* initial seed must be nonzero, don't use a static variable for the state if multithreaded */
    static uint64_t x = 1;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return x * 0x2545F4914F6CDD1DULL;
}
</source>

The generator fails only the ''MatrixRank'' test of BigCrush, however if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures.{{r|PCG|p=7}} In fact, a reduced version with only 40 bits of internal state passes the suite, suggesting a large safety margin.{{r|PCG|p=19}} A similar generator suggested in ''[[Software:Numerical Recipes|Numerical Recipes]]''<ref name="NR"/> as <code>RanQ1</code> also fails the ''BirthdaySpacings'' test.

Vigna<ref name="vigna" /> suggests the following {{em|xorshift1024*}} generator with 1024 bits of state and a maximal period of 2<sup>1024</sup>−1; however, it does not always pass BigCrush.{{r|Lemire19}} xoshiro256** is therefore a much better option.
<source lang="c">
#include <stdint.h>

/* The state must be seeded so that there is at least one non-zero element in array */
struct xorshift1024s_state {
	uint64_t x[16];
	int index;
};

uint64_t xorshift1024s(struct xorshift1024s_state *state)
{
	int index = state->index;
	uint64_t const s = state->x[index++];
	uint64_t t = state->x[index &= 15];
	t ^= t << 31;		// a
	t ^= t >> 11;		// b  -- Again, the shifts and the multipliers are tunable
	t ^= s ^ (s >> 30);	// c
	state->x[index] = t;
	state->index = index;
	return t * 1181783497276652981ULL;
}
</source>

===xorshift+===
An {{em|xorshift+}} generator can achieve an order of magnitude fewer failures than [[Mersenne Twister]] or [[Well equidistributed long-period linear|WELL]]. A native C implementation of an xorshift+ generator that passes all tests from the BigCrush suite can typically generate a random number in fewer than 10 clock cycles on [[X86|x86]], thanks to [[Instruction pipelining|instruction pipelining]].<ref name="shootout"/>

Rather than using multiplication, it is possible to use addition as a faster non-linear transformation. The idea was first proposed by Saito and Matsumoto (also responsible for the Mersenne Twister) in the {{em|XSadd}} generator, which adds two consecutive outputs of an underlying {{em|xorshift}} generator based on 32-bit shifts.<ref name="xsadd"/> However, one disadvantage of adding consecutive outputs is that, while the underlying {{em|xorshift128}} generator is 2-dimensionally equidistributed, the {{em|xorshift128+}} generator is only 1-dimensionally equidistributed.<ref name="vigna2"/>

{{em|XSadd}} has some weakness in the low-order bits of its output; it fails several BigCrush tests when the output words are bit-reversed.  To correct this problem, Vigna introduced the {{em|xorshift+}} family,<ref name="vigna2"/> based on 64-bit shifts. {{em|xorshift+}} generators, even as large as {{em|xorshift1024+}}, exhibit some detectable linearity in the low-order bits of their output;{{r|Lemire19}} it passes BigCrush, but doesn't when the 32 lowest-order bits are used in reverse order from each 64-bit word.{{r|Lemire19}} This generator is one of the fastest generators passing BigCrush.<ref name="shootout"/>

The following {{em|xorshift128+}} generator uses 128 bits of state and has a maximal period of 2<sup>128</sup>−1.
<source lang="c">
#include <stdint.h>

struct xorshift128p_state {
    uint64_t x[2];
};

/* The state must be seeded so that it is not all zero */
uint64_t xorshift128p(struct xorshift128p_state *state)
{
	uint64_t t = state->x[0];
	uint64_t const s = state->x[1];
	state->x[0] = s;
	t ^= t << 23;		// a
	t ^= t >> 18;		// b -- Again, the shifts and the multipliers are tunable
	t ^= s ^ (s >> 5);	// c
	state->x[1] = t;
	return t + s;
}
</source>

==xoshiro==
xoshiro and xoroshiro use rotations in addition to shifts. According to Vigna, they are faster and produce better quality output than xorshift.{{r|xoshiro-web|xoshiro-paper}}

This class of generator has variants for 32-bit and 64-bit integer and floating point output; for floating point, one takes the upper 53 bits (for [[Double-precision floating-point format|binary64]]) or the upper 23 bits (for [[Single-precision floating-point format|binary32]]), since the upper bits are of better quality than the lower bits in the floating point generators. The algorithms also include a <code source="C">jump</code> function, which sets the state forward by some number of steps – usually a power of two that allows many [[Thread (computing)|threads of execution]] to start at distinct initial states.

For 32-bit output, xoshiro128** and xoshiro128+ are exactly equivalent to xoshiro256** and xoshiro256+, with {{mono|uint32_t}} in place of {{mono|uint64_t}}, and with different shift/rotate constants.

More recently, the {{mono|xoshiro++}} generators have been made as an alternative to the {{mono|xoshiro**}} generators. They are used in some implementations of [[Fortran]] compilers such as GNU Fortran, [[Java (programming language)|Java]], and [[Julia (programming language)|Julia]].<ref name="xoshiro">{{cite web|url=https://prng.di.unimi.it  |title=xoshiro / xoroshiro generators and the PRNG shootout|access-date=2023-09-07}}</ref>

===xoshiro256**===
xoshiro256** is the family's general-purpose random 64-bit number generator. It is used in [[Software:GNU Fortran|GNU Fortran]] [[Compiler|compiler]], [[Lua (programming language)|Lua]] (as of Lua 5.4), and the .NET framework (as of .NET 6.0).<ref name="xoshiro"/>

<source lang="c">
/*  Adapted from the code included on Sebastiano Vigna's website */

#include <stdint.h>

uint64_t rol64(uint64_t x, int k)
{
	return (x << k) | (x >> (64 - k));
}

struct xoshiro256ss_state {
	uint64_t s[4];
};

uint64_t xoshiro256ss(struct xoshiro256ss_state *state)
{
	uint64_t *s = state->s;
	uint64_t const result = rol64(s[1] * 5, 7) * 9;
	uint64_t const t = s[1] << 17;

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];

	s[2] ^= t;
	s[3] = rol64(s[3], 45);

	return result;
}
</source>

===xoshiro256+===
xoshiro256+ is approximately 15% faster than xoshiro256**, but the lowest three bits have low linear complexity; therefore, it should be used only for floating point results by extracting the upper 53 bits.

<source lang="c">
#include <stdint.h>

uint64_t rol64(uint64_t x, int k)
{
	return (x << k) | (x >> (64 - k));
}

struct xoshiro256p_state {
	uint64_t s[4];
};

uint64_t xoshiro256p(struct xoshiro256p_state *state)
{
	uint64_t* s = state->s;
	uint64_t const result = s[0] + s[3];
	uint64_t const t = s[1] << 17;

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];

	s[2] ^= t;
	s[3] = rol64(s[3], 45);

	return result;
}
</source>

===xoroshiro===
If space is at a premium, xoroshiro128** and xoroshiro128+ are equivalent to xoshiro256** and xoshiro256+. These have smaller state spaces, and thus are less useful for massively parallel programs. xoroshiro128+ also exhibits a mild dependency in the [[Hamming weight|population count]], generating a failure after {{val|5|ul=TB}} of output. The authors do not believe that this can be detected in real world programs.

xoroshiro64** and xoroshiro64* are equivalent to xoroshiro128** and xoroshiro128+. Unlike the xoshiro generators, they are not straightforward ports of their higher-precision counterparts.

==Initialization==
In the xoshiro paper, it is recommended to initialize the state of the generators using a generator which is radically different from the initialized generators, as well as one which will never give the "all-zero" state; for shift-register generators, this state is impossible to escape from.<ref name="xoshiro-paper"/><ref name="initialization"/> The authors specifically recommend using the SplitMix64 generator, from a 64-bit seed, as follows:

<source lang="c">
#include <stdint.h>

struct splitmix64_state {
	uint64_t s;
};

uint64_t splitmix64(struct splitmix64_state *state) {
	uint64_t result = (state->s += 0x9E3779B97f4A7C15);
	result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
	result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
	return result ^ (result >> 31);
}

struct xorshift128_state {
    uint32_t x[4];
};

// one could do the same for any of the other generators
void xorshift128_init(struct xorshift128_state *state, uint64_t seed) {
	struct splitmix64_state smstate = {seed};

	uint64_t tmp = splitmix64(&smstate);
	state->x[0] = (uint32_t)tmp;
	state->x[1] = (uint32_t)(tmp >> 32);

	tmp = splitmix64(&smstate);
	state->x[2] = (uint32_t)tmp;
	state->x[3] = (uint32_t)(tmp >> 32);
}
</source>

==Notes==
{{notelist}}

==References==
{{reflist|refs =
<ref name="marsaglia">{{cite journal
| title=Xorshift RNGs
| journal=[[Journal of Statistical Software]]
| volume=8 | issue=14
| date=July 2003
| doi=10.18637/jss.v008.i14| doi-access=free
}}</ref>
<ref name="brent">{{cite journal
| title=Note on Marsaglia's Xorshift Random Number Generators
| journal=[[Journal of Statistical Software]]
| volume=11 | issue=5
| date=August 2004
| doi=10.18637/jss.v011.i05| doi-access=free
| hdl=1885/34049
| hdl-access=free
}}</ref>
<ref name="panne">{{cite journal
| first1=François | last1=Panneton
| first2=Pierre | last2=L'Ecuyer
| title=On the xorshift random number generators
| journal=ACM Transactions on Modeling and Computer Simulation
| volume=15 | issue=4
| pages=346–361
| date=October 2005
| url=https://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
| doi=10.1145/1113316.1113319| s2cid=11136098
}}</ref>
<ref name="NR">{{Cite book 
| last3=Vetterling | first3=WT
| last4=Flannery | first4=BP
| year=2007
| title=Numerical Recipes: The Art of Scientific Computing
| edition=3rd
| publisher=Cambridge University Press
| location=New York
| isbn=978-0-521-88068-8
| chapter=Section 7.1.2.A. 64-bit Xorshift Method
| chapter-url=http://apps.nrbook.com/empanel/index.html#pg=345
}}</ref>
<ref name="shootout">{{cite web
| last=Vigna | first=Sebastiano
| title=xorshift*/xorshift+ generators and the PRNG shootout
| url=http://prng.di.unimi.it
| access-date=2014-10-25}}</ref>
<ref name="vigna">
{{cite journal
| last=Vigna | first=Sebastiano
| title=An experimental exploration of Marsaglia's xorshift generators, scrambled
| journal=ACM Transactions on Mathematical Software
| volume=42 | issue=4 | date=July 2016 | page=30<!--Actually article number-->
| doi=10.1145/2845077
| arxiv=1402.6246
| s2cid=13936073
| url=http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
}}  Proposes xorshift* generators, adding a final multiplication by a constant.</ref>
<ref name="vigna2">{{cite journal
| last=Vigna | first=Sebastiano
| title=Further scramblings of Marsaglia's xorshift generators
| journal=Journal of Computational and Applied Mathematics
| volume=315 | issue=C | date=May 2017 | pages=175–181 
| doi=10.1016/j.cam.2016.11.006
| arxiv=1404.0390
| s2cid=6876444
| url=http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
}}  Describes xorshift+ generators, a generalization of XSadd.</ref>
<ref name="xsadd">{{cite web
| title=XORSHIFT-ADD (XSadd): A variant of XORSHIFT
| first1=Mutsuo | last1=Saito
| first2=Makoto | last2=Matsumoto
| year=2014
| url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/XSADD/
| access-date=2014-10-25}}</ref>
<ref name="xoshiro-web">{{cite web
| title=xoshiro/xoroshiro generators and the PRNG shootout
| last=Vigna | first=Sebastiano
| url=http://xoroshiro.di.unimi.it
| access-date=2019-07-07}}</ref>
<ref name="xoshiro-paper">{{cite journal
| title=Scrambled Linear Pseudorandom Number Generators
| last1=Blackman | first1=David
| last2=Vigna | first2=Sebastiano
| year=2018
| journal=Data Structures and Algorithms 
| arxiv=1805.01407 }}</ref>
<ref name="initialization">{{cite journal
| first1=Makoto | last1=Matsumoto
| first2=Isaku | last2=Wada
| first3=Ai | last3=Kuramoto
| first4=Hyo | last4=Ashihara
| title=Common defects in initialization of pseudorandom number generators
| journal=ACM Transactions on Modeling and Computer Simulation
| volume=17 | issue=4
| pages=15–es
| date=September 2007
| doi=10.1145/1276927.1276928| s2cid=1721554
}}</ref>
<ref name="PCG">{{cite tech report
 |title=PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
 |first=Melissa E. |last=O'Neill
 |publisher=[[Organization:Harvey Mudd College|Harvey Mudd College]]
 |id=HMC-CS-2014-0905
 |date=5 September 2014
 |pages=6–8
 |url=http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf}}</ref>
<ref name="Lemire19">{{cite journal
| first1=Daniel | last1=Lemire
| first2=Melissa E. |last2=O’Neill
| title=Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity
| journal=Computational and Applied Mathematics
| volume=350 |pages=139–142 |date=April 2019
| doi=10.1016/j.cam.2018.10.019 |arxiv=1810.05313
| s2cid=52983294
| quote=We report that these scrambled generators systematically fail Big Crush—specifically the linear-complexity and matrix-rank tests that detect linearity—when taking the 32 lowest-order bits in reverse order from each 64-bit word.}}</ref>
}}

==Further reading==
*{{Cite journal
| title=Some long-period random number generators using shifts and xors
| url=https://maths-people.anu.edu.au/~brent/pub/pub224.html
| date=July 2006
| journal=ANZIAM Journal
| volume=48 |ref=none
| pages=C188–C202}}  Lists generators of various sizes with four shifts (two per feedback word).

[[Category:Pseudorandom number generators]]

{{Sourceattribution|Xorshift}}