Xorshift

The Xorshift generators are a class of modern pseudo random number generators . Due to the low demands on memory and processor, they are also suitable for use on systems with low resources, e.g. B. Embedded Systems . The Xorshift generator was presented in 2003 by its developer George Marsaglia .

properties

simple: only uses the bit operations Shift and XOR;
low memory requirement: just as much as is necessary on principle for the desired period length (see below);
scalable: the number of status words can be freely selected in order to obtain the desired period length;
fast: a word is generated with only six to seven bit operations ;
only suitable for smaller amounts of random numbers: fails in some statistical tests of the TestU01 suite
not cryptographically secure because the internal state is open.

theory

The state of the generator is a bit vector with bits , which is multiplied with a binary n × n matrix to calculate the next state . The elements are calculated modulo 2 in the body GF (2) . The addition of elements (bits) becomes an XOR link and the multiplication becomes an AND link. The period length of the generator is when initialized with a value other than zero and the matrix is selected appropriately. This is achieved with precisely those matrices that have the element order in the general linear group GL (n, 2) (the group of invertible binary n × n matrices with multiplication ) . ${\ displaystyle b \ in \ {0.1 \} ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle 2 ^ {n} -1}$ ${\ displaystyle b}$ ${\ displaystyle 2 ^ {n} -1}$

The matrix is also constructed so the multiplication with the state vector that easily and efficiently with few machine operations ( bit shift , and bit by bit XOR ) can run. The developers assumed such representations in machine operations and checked whether the multiplication matrix thus defined had the element order . ${\ displaystyle \ ll}$ ${\ displaystyle \ gg}$ ${\ displaystyle \ oplus}$ ${\ displaystyle 2 ^ {n} -1}$

It turned out that if a computer word is with or bit, then the three consecutive operations correspond ${\ displaystyle b}$ ${\ displaystyle n = 32}$ ${\ displaystyle n = 64}$

{\ displaystyle b \ leftarrow b \ oplus (b \ ll u)}

{\ displaystyle b \ leftarrow b \ oplus (b \ gg v)}

{\ displaystyle b \ leftarrow b \ oplus (b \ ll w)}

a multiplication by a matrix of the order if the constant shift widths are chosen appropriately. ${\ displaystyle 2 ^ {n} -1}$ ${\ displaystyle u, v, w}$

In order to obtain longer periods than , the state of the generator can also be represented with several words: ${\ displaystyle 2 ^ {64} -1}$

{\ displaystyle h \ leftarrow b_ {ia} \ oplus (b_ {ia} \ ll u);}

{\ displaystyle b_ {i} \ leftarrow h \ oplus (h \ gg v) \ oplus b_ {i-1} \ oplus (b_ {i-1} \ gg w); \ quad i = a, a + 1, \ dots}

The state of this generator is given by the words ( to are the seed values). Thus, if the word length is, the state contains bits. Again, it is chosen so that the above operations correspond to a multiplication of the state vector with an n × n matrix of the element order , which results in the next state . After each such calculation step, the result is output and incremented. ${\ displaystyle a}$ ${\ displaystyle b_ {ia}, \ dots, b_ {i-1}}$ ${\ displaystyle b_ {0}}$ ${\ displaystyle b_ {a-1}}$ ${\ displaystyle e}$ ${\ displaystyle n = ae}$ ${\ displaystyle u, v, w}$ ${\ displaystyle 2 ^ {n} -1}$ ${\ displaystyle b_ {i-a + 1}, \ dots, b_ {i}}$ ${\ displaystyle b_ {i}}$ ${\ displaystyle i}$

As a rule, better random numbers are obtained if a somewhat more complex function of the state is output instead , for example with an odd constant multiplier or . ${\ displaystyle b_ {i}}$ ${\ displaystyle b_ {i-a + 1}, \ dots, b_ {i}}$ ${\ displaystyle c \ cdot b_ {i}}$ ${\ displaystyle c}$ ${\ displaystyle b_ {i} + b_ {i-1}}$

initialization

The initial state of the generator must not be zero; at least one of the status bits must have the value 1. Otherwise you get a generator with a period length of 1, which always outputs only 0, since a series of “0” can never result in a “1” only through shift and XOR operations. ${\ displaystyle n}$

Bad initialization, i.e. H. Only a few 1-bits in the state vector, the Xorshift recovers relatively quickly thanks to its (usually) small state vector. The probability of later encountering such states by chance is negligible due to the small number of these states compared to the period length.

implementation

uint32_t x32 = 314159265;
uint32_t xorshift32()
{
  x32 ^= x32 << 13;
  x32 ^= x32 >> 17;
  x32 ^= x32 << 5;
  return x32;
}

uint64_t x64 = 88172645463325252ull;
uint64_t xorshift64()
{
  x64 ^= x64 << 13;
  x64 ^= x64 >> 7;
  x64 ^= x64 << 17;
  return x64;
}

uint32_t x = 123456789;
uint32_t y = 362436069;
uint32_t z = 521288629;
uint32_t w = 88675123;
uint32_t xorshift128()
{
  uint32_t t = x ^ (x << 11);
  x = y; y = z; z = w;
  w ^= (w >> 19) ^ t ^ (t >> 8);
  return w;
}

Comparison with the `rand()`function from Libc

The rand () function available as standard under C (and C ++) is implemented as a linear congruence generator under Linux ( Glibc ) and Windows and delivers a sequence that does not pass even the simplest statistical tests. It is therefore not advisable to use it.

A Xorshift RNG in the form shown above is a quickly implemented alternative with only five variables, but it also fails some statistical tests.

Comparison with Mersenne Twister

The Xorshift generator is at least as good as, if not superior , to the Mersenne Twister :

The generated bit sequences are pseudo-random and evenly distributed in both cases, but the Mersenne twister passes almost all stochastic tests.

The memory requirement (for the state vector) is considerably lower (here: 16 bytes instead of 2496 bytes).

The Xorshift generator is also almost 60% faster.

If the initialization is poor (i.e. only one set bit in the state vector), the Xorshift needs less than 10 steps until it returns a uniformly distributed bit sequence. The Mersenne Twister needs almost 800,000 steps for this, which is also due to the larger state vector.

The Xorshift RNG has a shorter period length of 2 ¹²⁸ −1 than the Mersenne Twister with 2 ¹⁹⁹³⁷ −1. However, the significantly larger period length of the Mersenne twister does not really provide any information about the quality of a random number generator: A longer period does not mean a higher quality or better statistics as a result. In addition, there are other modern generators with even longer periods (up to ^{2131 086} ≈ 10 ³⁹⁴⁶¹ ) and in some ^cases superior properties (see CMWC and WELL ).

variants

Xorshift fails some tests in the BigCrush Test Suite ( TestU01 ). This applies to all generators based on linear operations such as Mersenne Twister or WELL . However, it is easy to scramble their outputs to improve their quality.

Xorwow

Marsaglia proposed to increase the period length by combining Xorshift with a simple numerator modulo 2 ³² (what he calls the "Weyl sequence"; according to Weyl's uniform distribution theorem: the sequence with irrational is uniformly distributed in the interval ). This generator has a period length of : ${\ displaystyle (a \ cdot i {\ bmod {1}}) _ {i \ in \ mathbb {N} ^ {+}}}$ ${\ displaystyle a}$ ${\ displaystyle {[0,1 [}}$ ${\ displaystyle (2 ^ {128} -1) \ cdot 2 ^ {32}}$

/* die ersten vier Wörter von state[] dürfen nicht komplett mit 0 initialisiert werden */
uint32_t xorwow(uint32_t state[static 5])
{
	/* Algorithmus "xorwow" von S. 5 in Marsaglia, "Xorshift RNGs" */
	uint32_t s, t = state[3];
	t ^= t >> 2;
	t ^= t << 1;
	state[3] = state[2]; state[2] = state[1]; state[1] = s = state[0];
	t ^= s;
	t ^= s << 4;
	state[0] = t;
	return t + (state[4] += 362437);
}

Xorwow is fast, but BigCrush fails some tests. It is the standard generator in Nvidia's CUDA .

Xorshift *

Xorshift * arises from a normal Xorshift by modulating or multiplying the output with a constant (suggested by Marsaglia). The following generator with 64 status bits has the period length and only fails in the MatrixRank test from BigCrush: ${\ displaystyle 2 ^ {32}}$ ${\ displaystyle 2 ^ {64}}$ ${\ displaystyle 2 ^ {64} -1}$

#include <stdint.h>

uint64_t xorshift64star(uint64_t & state) {
	uint64_t x = state;	/* state nicht mit 0 initialisieren */
	x ^= x >> 12; // a
	x ^= x << 25; // b
	x ^= x >> 27; // c
	state = x;
	return x * 0x2545F4914F6CDD1D;
}

A similar generator is suggested in Numerical Recipes as RanQ1 ; but it also fails the BirthdaySpacings test.

If you let Xorshift * print only the 32 most significant bits of the result, BigCrush passes it without errors. There is still a safety reserve, as these tests have already been passed by a version of the generator with only 40 status bits.

Vigna suggests the following Xorshift1024 *, with 1024 status bits and a period of BigCrush: ${\ displaystyle 2 ^ {1024} -1}$

#include <stdint.h>

static uint64_t s[16]; // nicht komplett mit 0 initialisieren
static int p;

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

Xorshift +

Instead of multiplication, the usually faster addition can also be used as a non-linear transformation. This idea was first suggested by Saito and Matsumoto (who also created the Mersenne Twister ) in the XSadd generator, which adds two consecutive outputs of an underlying Xorshift.

XSadd has weaknesses in the less significant output bits and fails in some BigCrush tests if the output words are inverted, i.e. the least significant bits are put in the highest position and vice versa. As a remedy, Vigna has designed the Xorshift + family that work with 64-bit words: the following Xorshift128 + uses 128 status bits and has a period length of . It passes BigCrush, even with inversion. ${\ displaystyle 2 ^ {128} -1}$

#include <stdint.h>

uint64_t s[2]; // nicht komplett mit 0 initialisieren

uint64_t xorshift128plus(void) {
	uint64_t x = s[0];
	uint64_t const y = s[1];
	s[0] = y;
	x ^= x << 23; // a
	s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
	return s[1] + y;
}

It's one of the fastest generators that BigCrush can make. A disadvantage of adding successive output words is that the generator is only evenly distributed in one dimension, although this applies to the underlying Xorshift in 2 dimensions

Xoroshiro and Xoshiro

Developed by Sebastiano Vigna and David Blackman, these generators are based on the same theory as Xorshift. However, they also contain bit rotation as an elementary operation. Subsequent versions have a period length of . ${\ displaystyle 2 ^ {128} -1}$

#include <stdint.h>

inline uint64_t rotl (uint64_t a, int w) {
   return a << w | a >> (64-w);
}

uint64_t xoroshiro128plus(void) {
   static uint64_t s0 = 1451815097307991481;
   static uint64_t s1 = 5520930533486498032; // auch hier wieder nicht beide mit 0 initialisieren

   const uint64_t result = s0 + s1;

   s1 ^= s0;
   s0 = rotl(s0, 55) ^ s1 ^ (s1 << 14);
   s1 = rotl(s1, 36);

   return result;
}

uint64_t xoroshiro128starstar(void) {
   static uint64_t s0 = 1321861022983091513;
   static uint64_t s1 = 3123198108391880477; // auch hier wieder nicht beide mit 0 initialisieren

   const uint64_t result = rotl(s0 * 5, 7) * 9;

   s1 ^= s0;
   s0 = rotl(s0, 24) ^ s1 ^ (s1 << 16);
   s1 = rotl(s1, 37);

   return result;
}

Xoshiro is the further developed variant that generates even better random numbers and has a period length of . ${\ displaystyle 2 ^ {256} -1}$

#include <stdint.h>

inline uint64_t rotl (uint64_t a, int w) {
   return a << w | a >> (64-w);
}

uint64_t xoshiro256(void) {
   static uint64_t s0 = 1321861022983091513;
   static uint64_t s1 = 3123198108391880477; // nicht alle vier mit 0 initialisieren
   static uint64_t s2 = 1451815097307991481;
   static uint64_t s3 = 5520930533486498032;

   const uint64_t result = s0 + s3; // alternativ: result = rotl(s1 * 5, 7) * 9

   const uint64_t t = s1 << 17;
   s2 ^= s0;
   s3 ^= s1;
   s1 ^= s2;
   s0 ^= s3;
   s2 ^= t;
   s3 = rotl(s3, 45);

   return result;
}

literature

G. Marsaglia: Random number generators . (PDF) In: Journal of Modern Applied Statistical Methods , Vol. 2, 2003, pp. 2-13.
G. Marsaglia: On the randomness of Pi and other decimal expansions . (PDF) Interstat, October 2005, # 5

Individual evidence

↑ ^a ^b ^c George Marsaglia: Xorshift RNGs
↑ Library with statistical tests: TestU01
↑ Pierre L'Ecuyer, Richard Simard: TestU01 ACM Paper , p. 29
^ F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2 . (PDF; 301 kB)
↑ Fabien Le Floc'h: XORWOW L'ecuyer TestU01 Results . January 12, 2011. Retrieved November 2, 2017.
↑ cuRAND testing . Nvidia . Retrieved November 2, 2017.
↑ ^a ^b Xorshift *: An experimental exploration of Marsaglia's xorshift generators, scrambled
^ Book "Numerical Recipes: The Art of Scientific Computing", Press / Teukolsky / Vetterling / Flannery, 2007, Cambridge University Press. Chapter: 7.1.2.A. 64-bit Xorshift Method
↑ PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
↑ XORSHIFT-ADD (XSadd): A variant of XORSHIFT
↑ ^a ^b Xorshift + Generatoren: Further scramblings of Marsaglia's xorshift generators
↑ xorshift * / xorshift + generators and the PRNG shootout
^ David Blackman, Sebastiano Vigna: Scrambled Linear Pseudorandom Generators . 2018. Retrieved April 14, 2018.
↑ David Blackman, Sebastiano Vigna: Original C source code implementation of Xoroshiro128 + . 2016. Retrieved July 21, 2017.
↑ http://xoshiro.di.unimi.it

[xorshift_paper-1] George Marsaglia: Xorshift RNGs

[testu01-2] Library with statistical tests: TestU01

[testu01_paper-3] Pierre L'Ecuyer, Richard Simard: TestU01 ACM Paper , p. 29

[well_paper-4] F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2 . (PDF; 301 kB)

[5] Fabien Le Floc'h: XORWOW L'ecuyer TestU01 Results . January 12, 2011. Retrieved November 2, 2017.

[6] uRAND testing . Nvidia . Retrieved November 2, 2017.

[vigna-7] Xorshift *: An experimental exploration of Marsaglia's xorshift generators, scrambled

[NR-8] Book "Numerical Recipes: The Art of Scientific Computing", Press / Teukolsky / Vetterling / Flannery, 2007, Cambridge University Press. Chapter: 7.1.2.A. 64-bit Xorshift Method

[techreport-9] PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation

[xsadd-10] XORSHIFT-ADD (XSadd): A variant of XORSHIFT

[vigna2-11] Xorshift + Generatoren: Further scramblings of Marsaglia's xorshift generators

[shootout-12] xorshift * / xorshift + generators and the PRNG shootout

[xoroshiro-13] David Blackman, Sebastiano Vigna: Scrambled Linear Pseudorandom Generators . 2018. Retrieved April 14, 2018.

[xoroshiro-imp-14] David Blackman, Sebastiano Vigna: Original C source code implementation of Xoroshiro128 + . 2016. Retrieved July 21, 2017.

[xoshiro-15] ttp://xoshiro.di.unimi.it

Xorshift

contents

properties

theory

initialization

implementation

Comparison with the `rand()`function from Libc

Comparison with Mersenne Twister

variants

Xorwow

Xorshift *

Xorshift +

Xoroshiro and Xoshiro

See also

literature

Individual evidence

Xorshift

properties

theory

initialization

implementation

Comparison with the rand()function from Libc

Comparison with Mersenne Twister

variants

Xorwow

Xorshift *

Xorshift +

Xoroshiro and Xoshiro

See also

literature

Individual evidence

Comparison with the `rand()`function from Libc