Xorshift

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 († 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.);
  • 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[2][3]
  • nicht kryptographisch sicher, da der interne Zustand offen liegt.

Theorie[Bearbeiten | Quelltext bearbeiten]

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 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. Dafür ist folgendes Berechnungsschema geeignet:

Der Zustand des Generators ist durch die Wörter mit jeweils Bit gegeben und enthält 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. bis sind die Saatwerte des Generators.

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 .[1]

Initialisierung[Bearbeiten | Quelltext bearbeiten]

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[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).

Varianten[Bearbeiten | Quelltext bearbeiten]

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

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.[5] Er ist der Standardgenerator in Nvidia's CUDA.[6]

Xorshift*[Bearbeiten | Quelltext bearbeiten]

Xorshift* entsteht aus einem normalen Xorshift, indem man die Ausgabe mit einer Konstanten modulo bzw. multipliziert (von Marsaglia vorgeschlagen).[1] Der folgende Generator mit 64 Zustandsbits hat die Periodenlänge [7] 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[8]; 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.[9]

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

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.[10]

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[11] 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.[12] 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[11]

Xoroshiro[Bearbeiten | Quelltext bearbeiten]

Diese von Sebastiano Vigna und David Blackman entwickelten Generatoren basieren auf der gleichen Theorie wie Xorshift.[13] Sie enthalten jedoch auch die Bitrotation als elementare Operation. Nachfolgende Version hat eine Periodenlänge von .[14]

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b c 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)
  5. Fabien Le Floc'h: XORWOW L'ecuyer TestU01 Results. 12 January 2011. Abgerufen am 2. November 2017.
  6. cuRAND Testing. Nvidia. Abgerufen am 2. November 2017.
  7. a b Xorshift*: An experimental exploration of Marsaglia's xorshift generators, scrambled
  8. Buch „Numerical Recipes: The Art of Scientific Computing“, Press/Teukolsky/Vetterling/Flannery, 2007, Cambridge University Press. Kapitel: 7.1.2.A. 64-bit Xorshift Method
  9. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
  10. XORSHIFT-ADD (XSadd): A variant of XORSHIFT
  11. a b Xorshift+ Generatoren: Further scramblings of Marsaglia's xorshift generators
  12. xorshift*/xorshift+ generators and the PRNG shootout
  13. David Blackman, Sebastiano Vigna: Scrambled Linear Pseudorandom Generators. 2018.
  14. David Blackman, Sebastiano Vigna: Original C source code implementation of Xoroshiro128+. 2016.