# Xorshift

Xorshift random number generators form a class of pseudorandom number generators that was discovered by George Marsaglia.[1] They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit shifted version of itself. This makes them extremely fast on modern computer architectures. The xor shift primitive is invertible.[2] They are a subclass of linear feedback shift registers, but their simple implementation typically makes them faster and use less space.[3] However, the parameters have to be chosen very carefully in order to achieve a long period.[4]

The xorshift generators have been shown to be fast but not reliable.[5] However, combining them with a nonlinear generator, as originally suggested by Marsaglia, leads to some of the fastest generators passing strong statistical tests.[6]

## Example implementation

A C version[note 1] of one xorshift algorithm [1] is:

```#include <stdint.h>

/* These state variables must be initialized so that they are not all zero. */

uint32_t x, y, z, w;

uint32_t xor128(void) {
uint32_t t;

t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}
```

This algorithm has a maximal period of 2128 − 1[4] and passes the diehard tests. However, it fails the MatrixRank and LinearComp tests of the BigCrush test suite from the TestU01 framework.

## Variations

All xorshift generators fail some test out of TestU01's BigCrush test suite (this is true of 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.

A xorshift* generator applies a multiplication to the output of a xorshift generator, as suggested by Marsaglia. The following 64-bit generator with 64 bits of state has a maximal period of 264 − 1[7] and fails only the MatrixRank test of BigCrush:

```#include <stdint.h>

uint64_t x; /* The state must be seeded with a nonzero value. */

uint64_t next() {
x ^= x >> 12; // a
x ^= x << 25; // b
x ^= x >> 27; // c
return x * 2685821657736338717LL;
}
```

A similar generator is suggested in Numerical Recipes,[8] but it fails also the BirthdaySpacings test.

The following generator, instead, has 1024 bits of state, a maximal period of 21024 − 1[7] and passes BigCrush:

```#include <stdint.h>

/* The state must be seeded so that it is not everywhere zero. If you have
a 64-bit seed,  we suggest to seed a xorshift64* generator and use its
output to fill s. */

uint64_t s[ 16 ];
int p;

uint64_t next(void) {
uint64_t s0 = s[ p ];
uint64_t s1 = s[ p = ( p + 1 ) & 15 ];
s1 ^= s1 << 31; // a
s1 ^= s1 >> 11; // b
s0 ^= s0 >> 30; // c
return ( s[ p ] = s0 ^ s1 ) * 1181783497276652981LL;
}
```

Both generators, as all xorshift* generators of maximal period, emit a sequence of 64-bit values that is equidistributed in the maximum possible dimension.[7]

The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2128 − 1[9] and passes BigCrush:

```#include <stdint.h>

/* The state must be seeded so that it is not everywhere zero. */

uint64_t s[ 2 ];

uint64_t next(void) {
uint64_t s1 = s[ 0 ];
const uint64_t s0 = s[ 1 ];
s[ 0 ] = s0;
s1 ^= s1 << 23;
return ( s[ 1 ] = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) ) ) + s0;
}
```

This generator is one of the fastest generator passing BigCrush;[6] however, it is only 1-dimensionally equidistributed.[9] It is a variation of the XSadd generator,[10] which however fails several BigCrush tests when reversed.

## Uses

WebKit's JavaScript Core (and hence Apple's Safari browser) uses the Xorshift RNG to supply random numbers for Math.random() in client JavaScript.[11]

## Notes

1. ^ In C, the "`^`" caret represents the Bitwise XOR, and " `<<` " the bit shift.

## References

1. ^ a b Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software 8 (14).
2. ^ Rivest, R. (2010). "The invertibility of the XOR of rotations of a binary word". International Journal of Computer Mathematics: 1–0. doi:10.1080/00207161003596708. edit
3. ^ Brent, Richard P. (August 2004). "Note on Marsaglia’s Xorshift Random Number Generators". Journal of Statistical Software 11 (5).
4. ^ a b Panneton, François (October 2005). "On the xorshift random number generators". ACM Transactions on Modeling and Computer Simulation (TOMACS) 15 (4).
5. ^ http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf See 8. Conclusion
6. ^ a b
7. ^ a b c Vigna, Sebastiano (2014). "An experimental exploration of Marsaglia's xorshift generators, scrambled". arXiv:abs/1402.6246.
8. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 7.1.2.A. 64-bit Xorshift Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
9. ^ a b Vigna, Sebastiano (2014). "Further scramblings of Marsaglia's xorshift generators". arXiv:abs/1404.0390.
10. ^
11. ^ Bortz, Andrew (7 March 2013). "Bug 111533 - Replace Mersenne Twister RNG with a simple but fast RNG". WebKit. Retrieved 2 January 2014.