Xorshift

Der Xorshift-Generator ist eine Klasse moderner Pseudozufallszahlengeneratoren. Er generiert sehr schnell und einfach eine gleichverteilte Sequenz an Pseudozufallszahlen. Vorgestellt wurde der Xorshift-Generator im Jahr 2003 von seinem Entwickler George Marsaglia († 2011)^[1].

Eigenschaften

• generiert eine hochgradig gleichverteilte Bit-Sequenz, d. h. er besteht alle statistischen Tests der TestU01-Suite^[2] (beinhaltet auch Diehard),
• benutzt ausschließlich einfache Bit-Operationen: Shift und XOR,
• geringer Speicherbedarf (hier: 4 · 32-Bit-Integer = 16 Byte),
• sehr einfache Implementierung: nur sieben Bit-Operationen zur Generierung eines Wertes notwendig,
• kein kryptographisch sicherer Zufallszahlengenerator,
• Die Periodenlänge ergibt sich direkt aus der Länge des Zustandsvektors (hier: 4·32 Bit), Periodenlänge: 2¹²⁸−1 ≈ 3,4·10³⁸).

Durch geringe Anforderungen an Speicher und Prozessor ist er prädestiniert zum Einsatz auch auf langsamen CPUs.

Periodenlänge

Die Periodenlänge (oder auch Sequenzlänge) ergibt sich direkt aus der Anzahl k der Bits des internen Zustands. Der hier vorgestellte Xorshift-RNG besitzt eine Länge von l = 2^k−1 = 2¹²⁸−1 ≈ 3,4·10³⁸. Durch das (zufällige) Wählen der Startwerte kann die Sequenz nochmals um ebenso viele Schritte zyklisch verschoben werden.

Diese Periodenlänge genügt praktisch allen Anforderungen. Obwohl sie um viele Größenordnungen kürzer ist als beispielsweise die des Mersenne-Twisters (Periodenlänge ca. 10⁶⁰⁰¹), so macht auch eine Periodenlänge von über 10³⁸ es praktisch unmöglich, mehr als nur einen Bruchteil der Sequenz an Zufallszahlen zu entnehmen. Um die Sequenz beispielsweise innerhalb von 100 Jahren mit Hilfe von einer Million parallel arbeitender Rechner einmal komplett zu durchlaufen, müsste jeder einzelnen Rechner pro Sekunde mehr als hundert Trilliarden Zufallszahlen generieren^[3].

Initialisierung

Der interne Zustandsvektor (hier: die Variablen x, y, z, w) darf nicht ausschließlich mit Nullen initialisiert werden, sondern muss mindestens ein 1-Bit enthalten. Ansonsten erhält man einen Generator der Länge 1 mit der Sequenz {0}. Da nur durch Shift- und XOR-Operationen aus einer Serie von „0“ niemals eine „1“ hervorgehen kann, führt so jeder Schritt wieder in den Anfangszustand (0) zurück.

Implementierung

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

Um eine gleichverteilte Zufallszahl auf dem halboffenen Intervall [0...1) zu erhalten:

double Xorshift_real()
{
  return Xorshift() / ((double) UINT32_MAX + 1.0);
}

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 auch alle statistischen Tests 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 stochastisch (hinreichend) unabhängig und gleichverteilt. Xorshift besteht in der TestU01-Suite sogar die Tests auf lineare Komplexität, wohingegen der Mersenne-Twister hier durchfällt.
• 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.^[4]
• Der Xorshift-RNG hat mit 2¹²⁸ − 1 eine kürzere Periodenlänge als der Mersenne-Twister mit 2¹⁹⁹³⁷ − 1. Die nochmals deutlich größere Periodenlänge des Mersenne-Twisters mag auf den ersten Blick beeindruckend aussehen, 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 2¹³¹⁰⁸⁶ ≈ 10³⁹⁴⁶¹) und teils überlegenen Eigenschaften (vgl. CMWC und WELL).

Siehe auch

• Well Equidistributed Long-period Linear
• Complimentary Multiply-with-Carry

Einzelnachweise

1. ↑ George Marsaglia: Xorshift RNGs
2. ↑ Bibliothek mit statistischen Tests: TestU01
3. ↑ Rechnung: 3,4·10³⁸ / 100·365·24·60·60·10⁶ ≈ 1,08·10²³
4. ↑ F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2.

• G. Marsaglia, Random number generators, Journal of Modern Applied Statistical Methods, V. 2, May 2003. http://tbf.coe.wayne.edu/jmasm/vol2_no1.pdf
• G. Marsaglia, On the randomness of Pi and other decimal expansions, Interstat, October 2005, #5, http://interstat.statjournals.net/YEAR/2005/articles/0510005.pdf

Arithmetische Zufallszahlengeneratoren

Kongruenzgenerator (linearer, multiplikativer, gemischt linearer, Fibonacci-Generator) | Inverser Kongruenzgenerator | Blum-Blum-Shub-Generator | Mersenne-Twister | WELL | Xorshift