Xorshift
Die Xorshift-Generatoren bilden eine Klasse moderner Pseudozufallszahlengeneratoren. Durch geringe Anforderungen an Speicher und Prozessor sind sie auch für den Einsatz auf Systemen mit geringen Ressourcen, z. B. Eingebettete Systeme, geeignet. Vorgestellt wurde der Xorshift-Generator im Jahr 2003 von seinem Entwickler George Marsaglia.

Eigenschaften 
 einfach: benutzt ausschließlich die Bit-Operationen Shift und XOR;
 geringer Speicherbedarf: gerade so viel, wie für die gewünschte Periodenlänge aus Prinzip nötig ist (s. u.);
 skalierbar: die Zahl der Zustandswörter ist frei wählbar, um die gewünschte Periodenlänge zu erhalten;
 schnell: mit nur sechs bis sieben Bit-Operationen wird ein Wort generiert;
 nur für kleinere Mengen von Zufallszahlen geeignet: scheitert an einigen statistischen Tests der TestU01-Suite
 nicht kryptographisch sicher, da der interne Zustand offen liegt.

Theorie 
Der Zustand des Generators ist ein Bitvektor  mit  Bit, der zur Berechnung des nächsten Zustandes mit einer binären n×n Matrix multipliziert wird. Mit den Elementen wird dabei modulo 2 gerechnet im Körper GF(2). Die Addition von Elementen (Bits) wird dabei zur XOR-Verknüpfung und die Multiplikation zur UND-Verknüpfung. Die Periodenlänge des Generators beträgt , wenn  mit einem von Null verschiedenen Wert initialisiert und die Matrix geeignet gewählt wird. Dies wird mit genau den Matrizen erreicht, die in der Allgemeinen linearen Gruppe GL(n,2) (der Gruppe der invertierbaren binären n×n Matrizen mit der Multiplikation) die Elementordnung  haben.

Die Matrix wird außerdem so konstruiert, dass sich die Multiplikation mit dem Zustandsvektor einfach und effizient mit wenigen Maschinenoperationen (Bitverschiebung ,  und bitweise XOR-Verknüpfung ) ausführen lässt. Die Entwickler gingen von solchen Darstellungen in Maschinenoperationen aus und prüften, ob die dadurch definierte Multiplikationsmatrix die Elementordnung  hat.

Es zeigte sich: wenn  ein Computerwort mit  oder  Bit ist, dann entsprechen die drei aufeinanderfolgenden Operationen

einer Multiplikation mit einer Matrix der Ordnung , wenn die konstanten Schiebeweiten  geeignet gewählt werden.

Um längere Perioden als  zu erhalten, kann man den Zustand des Generators auch mit mehreren Wörtern darstellen:

Der Zustand dieses Generators ist durch die  Wörter  gegeben ( bis  sind die Saatwerte). Wenn  die Wortlänge ist, enthält der Zustand somit  Bit. Es werden wiederum  so gewählt, dass obige Operationen eine Multiplikation des Zustandsvektors mit einer n×n-Matrix der Elementordnung  entsprechen, welche den nächsten Zustand  ergibt. Nach jedem solchen Rechenschritt wird  als Ergebnis ausgegeben und  inkrementiert.

Man erhält in der Regel bessere Zufallszahlen, wenn man statt  eine etwas komplexere Funktion des Zustands  ausgibt, zum Beispiel  mit einem ungeraden konstanten Multiplikator  oder .

Initialisierung 
Der Anfangszustand des Generators darf nicht Null sein; mindestens eines der  Zustandsbits muss den Wert 1 haben. Ansonsten erhält man einen Generator der Periodenlänge 1, der immer nur 0 ausgibt, da nur durch Shift- und XOR-Operationen aus einer Serie von „0“ niemals eine „1“ hervorgehen kann.

Von schlechter Initialisierung, d. h. nur wenige 1-Bits im Zustandsvektor, erholt sich der Xorshift relativ schnell dank seines (in der Regel) kleinen Zustandsvektors. Die Wahrscheinlichkeit, später zufällig auf solche Zustände zu stoßen, ist wegen der geringen Zahl dieser Zustände im Vergleich zur Periodenlänge vernachlässigbar.

Implementierung 
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;
}

Vergleich mit der rand()-Funktion aus Libc 
Die unter C (und C++) standardmäßig verfügbare Funktion rand() ist unter Linux (Glibc) und Windows als linearer Kongruenzgenerator implementiert und liefert eine Sequenz, die nicht einmal die einfachsten statistischen Tests besteht. Es ist somit von der Verwendung abzuraten.

Ein Xorshift-RNG in der oben dargestellten Form ist mit lediglich fünf Variablen eine schnell implementierte Alternative, die jedoch auch einige statistische Tests nicht besteht.

Vergleich mit Mersenne-Twister 
Der Xorshift-Generator ist dem Mersenne-Twister zumindest ebenbürtig, wenn nicht sogar überlegen:

 Die generierten Bitsequenzen sind in beiden Fällen pseudozufällig und gleichverteilt, jedoch besteht der Mersenne-Twister nahezu alle stochastischen Tests.
 Der Speicherbedarf (für den Zustandsvektor) ist erheblich geringer (hier: 16 Bytes, statt 2496 Bytes).
 Auch ist der Xorshift-Generator knapp 60 % schneller.
 Bei schlechter Initialisierung (d. h. nur ein gesetztes Bit im Zustandsvektor) benötigt der Xorshift weniger als 10 Schritte, bis er wieder eine gleichverteilte Bit-Sequenz liefert. Der Mersenne-Twister benötigt hierzu fast 800.000 Schritte, was auch an dem größeren Zustandsvektor liegt.
 Der Xorshift-RNG hat mit 2128−1 eine kürzere Periodenlänge als der Mersenne-Twister mit 219937−1. Die nochmals deutlich größere Periodenlänge des Mersenne-Twisters liefert jedoch nicht wirklich eine Aussage über die Güte eines Zufallszahlengenerators: Eine längere Periode bedeutet nicht gleichzeitig eine höhere Güte oder im Ergebnis eine bessere Statistik. Darüber hinaus existieren andere moderne Generatoren mit noch längeren Perioden (bis zu 2131086 ≈ 1039461) und teils überlegenen Eigenschaften (vgl. CMWC und WELL).

Varianten 
Xorshift versagt bei einigen Tests der BigCrush Test Suite (TestU01). Das gilt für alle Generatoren, die auf linearen Operationen basieren, wie auch Mersenne Twister oder WELL. Es ist jedoch leicht, deren Ausgaben zu verwürfeln, um ihre Qualität zu verbessern.

Xorwow 
Marsaglia schlug vor, die Periodenlänge zu vergrößern, indem Xorshift mit einem einfachen Zähler modulo 232 kombiniert wird (was er als "Weyl Sequenz" bezeichnet; nach dem Gleichverteilungssatz von Weyl: die Folge  mit irrationalem  ist im Intervall  gleichverteilt). Dieser Generator hat eine Periodenlänge von :
/* 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 ist schnell, aber besteht einige Tests aus BigCrush nicht. Er ist der Standardgenerator in Nvidia's CUDA.

Xorshift* 
Xorshift* entsteht aus einem normalen Xorshift, indem man die Ausgabe mit einer Konstanten modulo  bzw.  multipliziert (von Marsaglia vorgeschlagen). Der folgende Generator mit 64 Zustandsbits hat die Periodenlänge  und versagt nur beim MatrixRank-Test aus BigCrush:

#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;
}
Ein ähnlicher Generator wird in Numerical Recipes als RanQ1 vorgeschlagen; er versagt aber ebenfalls beim BirthdaySpacings-Test.

Wenn man Xorshift* nur die 32 höchstwertigen Bits des Ergebnisses ausgeben lässt, besteht er BigCrush ohne Fehler. Dabei besteht noch eine Sicherheitsreserve, da diese Tests auch schon von einer Version des Generators mit nur 40 Zustandsbits bestanden werden.

Vigna schlägt folgenden Xorshift1024* vor, mit 1024 Zustandsbits und einer Periodenlänge von , der BigCrush besteht:
#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+ 
Statt der Multiplikation kann man auch die in der Regel schnellere Addition als nichtlineare Transformation einsetzen. Diese Idee wurde zuerst von Saito und Matsumoto (von denen auch der Mersenne Twister stammt) vorgeschlagen, und zwar im XSadd-Generator, der zwei aufeinanderfolgende Ausgaben eines zugrundeliegenden Xorshift addiert.

XSadd hat Schwächen in den niederwertigen Ausgabebits und fällt bei einigen BigCrush-Tests durch, wenn man die Ausgabewörter invertiert, also die niederwertigsten Bits an die höchste Stelle setzt und umgekehrt. Als Abhilfe hat Vigna die Xorshift+ Familie konstruiert, die mit 64-Bit-Wörtern arbeiten: nachfolgender Xorshift128+ nutzt 128 Zustandsbits und hat eine Periodenlänge von . Er besteht BigCrush, auch bei Invertierung.
#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;
}

Es ist einer der schnellsten Generatoren, die BigCrush bestehen. Ein Nachteil der Addition von aufeinanderfolgenden Ausgabewörtern ist, dass der Generator so nur noch in einer Dimension gleichverteilt ist, obwohl dies für den zugrundeliegenden Xorshift in 2 Dimensionen gilt

Xoroshiro und Xoshiro 
Diese von Sebastiano Vigna und David Blackman entwickelten Generatoren basieren auf der gleichen Theorie wie Xorshift. Sie enthalten jedoch auch die Bitrotation als elementare Operation. Nachfolgende Versionen haben eine Periodenlänge von .

#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 ist die weiterentwickelte Variante, die nochmals bessere Zufallszahlen erzeugt und eine Periodenlänge von  aufweist.

#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;
}

Siehe auch 
 Liste von Zufallszahlengeneratoren

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

Einzelnachweise 

Pseudozufallszahlengenerator