Xorshift

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Xorshift-Generator ist eine Klasse moderner Pseudozufallszahlengeneratoren. Durch geringe Anforderungen an Speicher und Prozessor ist er prädestiniert zum Einsatz auch auf langsamen CPUs. Vorgestellt wurde der Xorshift-Generator im Jahr 2003 von seinem Entwickler George Marsaglia († 2011).[1]

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • 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.);
  • schnell: mit nur sieben Bit-Operationen wird ein Wort generiert;
  • nur für kleinere Mengen von Zufallszahlen geeignet: scheitert an einigen statistischen Tests der TestU01-Suite[2][3]
  • nicht kryptographisch sicher, da der interne Zustand offen liegt.

Periodenlänge[Bearbeiten | Quelltext bearbeiten]

Die Periodenlänge (oder auch Sequenzlänge) ergibt sich direkt aus der Anzahl der Bits des internen Zustands zu 2k−1. Der unten vorgestellte Xorshift-RNG besitzt mit vier 32-Bit-Worten eine Periodenlänge von 2128−1 ≈ 3,4·1038 Worten. Eine solche Periodenlänge genügt allen praktischen Anforderungen. Durch den Startwert kann die Sequenz beliebig zyklisch verschoben werden.

Initialisierung[Bearbeiten | Quelltext bearbeiten]

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.

Von „schlechter“ Initialisierung, d. h. nur wenige 1-Bits im Zustandsvektor, erholt sich der Xorshift relativ schnell dank seines 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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.[4]
  • 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).

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. George Marsaglia: Xorshift RNGs
  2. Bibliothek mit statistischen Tests: TestU01
  3. Pierre L’Ecuyer, Richard Simard: TestU01 ACM Paper, S. 29
  4. F. Panneton, P. L’Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2. (PDF; 301 kB)