imported>Georg-Johann: /* Einzelnachweise */ TestU01 Weblink aktualisiert

2025-12-17T10:42:01Z

Einzelnachweise: TestU01 Weblink aktualisiert

Neue Seite

Die '''Xorshift'''-Generatoren bilden eine Klasse moderner [[Pseudozufallszahlengenerator]]en. Durch geringe Anforderungen an Speicher und Prozessor sind sie auch für den Einsatz auf Systemen mit geringen Ressourcen, z. B. [[Eingebettetes System|Eingebettete Systeme]], geeignet. Vorgestellt wurde der Xorshift-Generator im Jahr 2003 von seinem Entwickler [[George Marsaglia]].<ref name="xorshift_paper" />

== Eigenschaften ==
* einfach: benutzt ausschließlich die [[Bitweiser Operator|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 [[Datenwort|Wort]] generiert;
* nur für kleinere Mengen von Zufallszahlen geeignet: scheitert an einigen statistischen Tests der TestU01-Suite<ref name="testu01" /><ref name="testu01_paper">Pierre L’Ecuyer, Richard Simard: [http://dl.acm.org/citation.cfm?doid=1268776.1268777 TestU01 ACM Paper], S. 29</ref>
* nicht [[Kryptographisch sicherer Zufallszahlengenerator|kryptographisch sicher]], da der interne Zustand offen liegt.

== Theorie ==
Der Zustand des Generators ist ein Bitvektor <math>b \in \{0,1\}^n</math> mit <math>n</math> [[Bit]], der zur Berechnung des nächsten Zustandes mit einer binären n×n [[Matrix (Mathematik)|Matrix]] multipliziert wird. Mit den Elementen wird dabei [[Division mit Rest#Modulo|modulo]] 2 gerechnet im [[Endlicher Körper#Beispiel: Der Körper mit 2 Elementen|Körper GF(2)]]. Die Addition von Elementen (Bits) wird dabei zur XOR-Verknüpfung und die Multiplikation zur UND-Verknüpfung. Die [[Periodische Funktion|Periodenlänge]] des Generators beträgt <math>2^n-1</math>, wenn <math>b</math> mit einem von Null verschiedenen Wert initialisiert und die Matrix geeignet gewählt wird. Dies wird mit genau den Matrizen erreicht, die in der [[Allgemeine lineare Gruppe|Allgemeinen linearen Gruppe GL(n,2)]] (der [[Gruppe (Mathematik)|Gruppe]] der [[Reguläre Matrix|invertierbaren]] binären n×n Matrizen mit der [[Matrizenmultiplikation|Multiplikation]]) die [[Ordnung eines Gruppenelements|Elementordnung]] <math>2^n-1</math> haben.

Die Matrix wird außerdem so konstruiert, dass sich die Multiplikation mit dem Zustandsvektor einfach und effizient mit wenigen Maschinenoperationen ([[Schieberegister|Bitverschiebung]] <math>\ll</math>, <math>\gg</math> und bitweise [[Kontravalenz|XOR-Verknüpfung]] <math>\oplus</math>) ausführen lässt. Die Entwickler gingen von solchen Darstellungen in Maschinenoperationen aus und prüften, ob die dadurch definierte Multiplikationsmatrix die Elementordnung <math>2^n-1</math> hat.

Es zeigte sich: wenn <math>b</math> ein Computerwort mit <math>n=32</math> oder <math>n=64</math> Bit ist, dann entsprechen die drei aufeinanderfolgenden Operationen
:<math>b \leftarrow b \oplus (b \ll u)</math>
:<math>b \leftarrow b \oplus (b \gg v)</math>
:<math>b \leftarrow b \oplus (b \ll w)</math>
einer Multiplikation mit einer Matrix der Ordnung <math>2^n-1</math>, wenn die konstanten Schiebeweiten <math>u, v, w</math> geeignet gewählt werden.

Um längere Perioden als <math>2^{64}-1</math> zu erhalten, kann man den Zustand des Generators auch mit mehreren Wörtern darstellen:
:<math>h \leftarrow b_{i-a} \oplus (b_{i-a} \ll u);</math>
:<math>b_i \leftarrow h \oplus (h \gg v) \oplus b_{i-1} \oplus (b_{i-1} \gg w); \quad i=a,a+1,\dots</math>
Der Zustand dieses Generators ist durch die <math>a</math> Wörter <math>b_{i-a},\dots,b_{i-1}</math> gegeben (<math>b_0</math> bis <math>b_{a-1}</math> sind die Saatwerte). Wenn <math>e</math> die Wortlänge ist, enthält der Zustand somit <math>n = ae</math> Bit. Es werden wiederum <math>u, v, w</math> so gewählt, dass obige Operationen eine Multiplikation des Zustandsvektors mit einer n×n-Matrix der Elementordnung <math>2^n-1</math> entsprechen, welche den nächsten Zustand <math>b_{i-a+1},\dots,b_i</math> ergibt. Nach jedem solchen Rechenschritt wird <math>b_i</math> als Ergebnis ausgegeben und <math>i</math> inkrementiert.

Man erhält in der Regel bessere Zufallszahlen, wenn man statt <math>b_i</math> eine etwas komplexere Funktion des Zustands <math>b_{i-a+1},\dots,b_i</math> ausgibt, zum Beispiel <math>c \cdot b_i</math> mit einem ungeraden konstanten Multiplikator <math>c</math> oder <math>b_i + b_{i-1}</math>.<ref name="xorshift_paper" />

== Initialisierung ==
Der Anfangszustand des Generators darf nicht Null sein; mindestens eines der <math>n</math> 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 ==
<syntaxhighlight lang="C">
uint32_t x32 = 314159265;
uint32_t xorshift32()
{
x32 ^= x32 << 13;
x32 ^= x32 >> 17;
x32 ^= x32 << 5;
return x32;
}

uint64_t x64 = 88172645463325252ul;
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;
}
</syntaxhighlight>

== Vergleich mit der <code>rand()</code>-Funktion aus Libc ==
Die unter C (und C++) standardmäßig verfügbare Funktion rand() ist unter Linux ([[Glibc]]) und Windows als [[Linearer Kongruenzgenerator#Linearer Kongruenzgenerator|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.<ref name="well_paper" />
* 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. [[Multiply-with-carry#Complimentary Multiply-with-carry|CMWC]] und [[Well Equidistributed Long-period Linear|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 Equidistributed Long-period Linear|WELL]]. Es ist jedoch leicht, deren Ausgaben zu [[Verwürfelung|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 (Mathematik)|Folge]] <math>(a \cdot i \bmod 1)_{i \in \N^+}</math> mit [[Irrationale Zahl|irrationalem]] <math>a</math> ist im Intervall <math>{[0,1[}</math> gleichverteilt). Dieser Generator hat eine Periodenlänge von <math>(2^{128}-1) \cdot 2^{32}</math>:
<syntaxhighlight lang="C">
/* 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);
}
</syntaxhighlight>
Xorwow ist schnell, aber besteht einige Tests aus BigCrush nicht.<ref>{{cite web
|title=XORWOW L'ecuyer TestU01 Results
|url=https://chasethedevil.github.io/post/xorwow-lecuyer-testu01-results/
|date=2011-01-12
|website=Chase The Devil (blog)
|first=Fabien |last=Le Floc'h
|accessdate=2017-11-02
}}</ref> Er ist der Standardgenerator in Nvidias [[CUDA]].<ref>{{cite web
|url=http://docs.nvidia.com/cuda/curand/testing.html
|title=cuRAND Testing
|publisher=[[Nvidia]]
|accessdate=2017-11-02
}}</ref>

=== Xorshift* ===
Xorshift* entsteht aus einem normalen Xorshift, indem man die Ausgabe mit einer Konstanten modulo <math>2^{32}</math> bzw. <math>2^{64}</math> multipliziert (von Marsaglia vorgeschlagen).<ref name="xorshift_paper" /> Der folgende Generator mit 64 Zustandsbits hat die Periodenlänge <math>2^{64}-1</math><ref name="vigna" /> und versagt nur beim MatrixRank-Test aus BigCrush:

<syntaxhighlight lang="C">
#include <stdint.h>

uint64_t xorshift64star(uint64_t & x)
{
x ^= x >> 12; // a
x ^= x << 25; // b
x ^= x >> 27; // c
return x * 0x2545F4914F6CDD1D;
}
</syntaxhighlight>
Ein ähnlicher Generator wird in ''Numerical Recipes'' als ''RanQ1'' vorgeschlagen<ref name="NR" />; 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.<ref name="techreport" />

Vigna<ref name="vigna" /> schlägt folgenden Xorshift1024* vor, mit 1024 Zustandsbits und einer Periodenlänge von <math>2^{1024}-1</math>, der BigCrush besteht:
<syntaxhighlight lang="C">
#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];
p = (p + 1) & 15;
uint64_t s1 = s[p];
s1 ^= s1 << 31; // a
s1 ^= s1 >> 11; // b
s1 ^= s0 ^ (s0 >> 30); // c
s[p] = s1;
return s1 * (uint64_t)1181783497276652981;
}
</syntaxhighlight>

=== 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.<ref name="xsadd" />

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<ref name="vigna2" /> die Xorshift+ Familie konstruiert, die mit 64-Bit-Wörtern arbeiten: nachfolgender Xorshift128+ nutzt 128 Zustandsbits und hat eine Periodenlänge von <math>2^{128}-1</math>. Er besteht BigCrush, auch bei Invertierung.
<syntaxhighlight lang="C">
#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;
}
</syntaxhighlight>

Es ist einer der schnellsten Generatoren, die BigCrush bestehen.<ref name="shootout" /> 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.<ref name="vigna2" />

=== Xoroshiro und Xoshiro ===
Diese von Sebastiano Vigna und David Blackman entwickelten Generatoren basieren auf der gleichen Theorie wie Xorshift.<ref name="xoroshiro" /> Sie enthalten jedoch auch die [[Bitweiser Operator#Zyklische Verschiebung|Bitrotation]] als elementare Operation. Nachfolgende Versionen haben eine Periodenlänge von <math>2^{128}-1</math>.<ref name="xoroshiro-imp" />

<syntaxhighlight lang="C">
#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;
}
</syntaxhighlight>

Xoshiro ist die weiterentwickelte Variante, die nochmals bessere Zufallszahlen erzeugt und eine Periodenlänge von <math>2^{256}-1</math> aufweist.<ref name="xoshiro" />

<syntaxhighlight lang="C">
#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;
}
</syntaxhighlight>

== Siehe auch ==
* [[Liste von Zufallszahlengeneratoren]]

== Literatur ==
* G. Marsaglia: [https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf ''Random number generators''.] (PDF) In: ''Journal of Modern Applied Statistical Methods'', Vol. 2, 2003, S. 2–13.
* G. Marsaglia: {{Webarchiv|wayback=20110720154229|url=http://interstat.statjournals.net/YEAR/2005/articles/0510005.pdf|text=''On the randomness of Pi and other decimal expansions''}}. (PDF) Interstat, Oktober 2005, #5

== Einzelnachweise ==
<references>
<ref name="xorshift_paper">George Marsaglia: [http://www.jstatsoft.org/v08/i14/paper Xorshift RNGs]
</ref>
<ref name="testu01">Bibliothek mit statistischen Tests: [https://simul.iro.umontreal.ca/testu01/tu01.html TestU01]
</ref>
<ref name="well_paper">F. Panneton, P. L’Ecuyer: [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/lfsr04.pdf ''Improved Long-Period Generators Base on Linear Recurrences Modulo 2''.] (PDF; 301 kB)
</ref>
<ref name="xsadd">[http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/XSADD/ XORSHIFT-ADD (XSadd): A variant of XORSHIFT]
</ref>
<ref name="vigna">Xorshift*: [http://vigna.di.unimi.it/ftp/papers/xorshift.pdf An experimental exploration of Marsaglia's xorshift generators, scrambled]
</ref>
<ref name="vigna2">Xorshift+ Generatoren: [http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf Further scramblings of Marsaglia's xorshift generators]
</ref>
<ref name="shootout">[http://prng.di.unimi.it/ xorshift*/xorshift+ generators and the PRNG shootout]
</ref>
<ref name="NR">Buch „Numerical Recipes: The Art of Scientific Computing“, Press/Teukolsky/Vetterling/Flannery, 2007, Cambridge University Press. {{Webarchiv|url=http://apps.nrbook.com/empanel/index.html#pg=345 |wayback=20110811154417 |text=Kapitel: 7.1.2.A. 64-bit Xorshift Method |archiv-bot=2024-06-18 22:07:06 InternetArchiveBot }}</ref>
<ref name="techreport">[http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf#page=21 PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation]

</ref>
<ref name="xoroshiro">{{Cite web|url=https://arxiv.org/abs/1805.01407|title=Scrambled Linear Pseudorandom Generators|last=Blackman |first=David|last2=Vigna |first2=Sebastiano|date=2018|accessdate=2018-04-14}}
</ref>
<ref name="xoroshiro-imp">{{Cite web|url=http://vigna.di.unimi.it/xorshift/xoroshiro128plus.c|title=Original C source code implementation of Xoroshiro128+|last=Blackman |first=David|last2= Vigna |first2= Sebastiano|date=2016|accessdate=2017-07-21}}
</ref>
<ref name="xoshiro">http://xoshiro.di.unimi.it</ref>
</references>

[[Kategorie:Pseudozufallszahlengenerator]]

Xorshift - Versionsgeschichte

imported>Georg-Johann: /* Einzelnachweise */ TestU01 Weblink aktualisiert