Kann XorShift Null zurückgeben?

Question

Ich habe über die Xorshift PRNG Lesen vor allem das Papier here

Ein Typ here besagt, dass

Die Zahl liegt im Bereich [1, 2 ** 64). Beachten Sie, dass es nie 0.

Mit Blick auf den Code, der Sinn macht, wird:

uint64_t x; 
uint64_t next(void) { 
    x ^= x >> 12; // a 
    x ^= x << 25; // b 
    x ^= x >> 27; // c 
    return x * UINT64_C(2685821657736338717); 
} 

Wenn x würde Null sein als jede nächste Zahl Null sein würde. Aber würde das nicht weniger nützlich sein? Das übliche Verwendungsmuster wäre etwa min + rand() % (max - min) oder das Konvertieren der 64 Bits in 32 Bits, wenn Sie nur eine int benötigen. Aber wenn 0 nie zurückgegeben wird, könnte das ein ernstes Problem sein. Auch die Bits sind nicht 0 oder 1 mit der gleichen Wahrscheinlichkeit wie offensichtlich 0 fehlt so Nullen oder etwas weniger wahrscheinlich. Ich kann sogar keine Erwähnung davon auf Wikipedia finden, also vermisse ich etwas?

Also was ist eine gute/geeignete Möglichkeit, zufällige, gleichverteilte Zahlen aus XorShift64 * in einem bestimmten Bereich zu generieren?

Answer 1

Ich bin fast sicher, dass es eine x, für die der Xorshift Betrieb 0 zurück

Beweis:

Erstens haben wir diese Gleichungen:

a = x^(x >> 12); 
b = a^(a << 25); 
c = b^(b >> 27); 

sie Substituieren:

b = (x^x >> 12)^((x^x >> 12) << 25); 

c = b^(b >> 27) = ((x^x >> 12)^((x^x >> 12) << 25))^(((x^x >> 12)^((x^x >> 12) << 25)) >> 27); 

Wie Sie sehen können, obwohl c ist eine komplexe Gleichung, es ist perfekt abelian.

Es bedeutet, dass Sie die Bits von c als vollständig boolesche Ausdrücke der Bits von x ausdrücken können.

So können Sie einfach ein Gleichungssystem für die Bits b0, b1, b2, konstruieren ... so:

(Anmerkung: die Koeffizienten sind nur Beispiele, ich habe sie nicht berechnen, aber so würde es aussehen):

c0 = x1^!x32^x47 ... 
c1 = x23^x45^!x61 ... 
... 
c63 = !x13^... 

Von diesem Punkt haben Sie 64 Gleichungen und 64 Unbekannten. Sie können es einfach mit Gauss-elimination lösen, Sie werden immer eine einzige einzigartige Lösung haben.

Außer einigen seltenen Fällen, d. H. Wenn die Determinante der Koeffizienten des Gleichungssystems Null ist, aber in der Größe einer solchen großen Matrix sehr unwahrscheinlich ist.

Auch wenn es passiert, es würde bedeuten, dass Sie einen Informationsverlust in jeder Iteration haben, das heißt sie können nicht alle der 2^64 möglichen Werte von x, nur einige von ihnen bekommen.

Betrachten wir nun die viel wahrscheinlichere Möglichkeit, dass die Koeffizientenmatrix nicht Null ist. In diesem Fall haben Sie für alle möglichen 2^64 Werte von x alle möglichen 2^64 Werte von c, und diese sind alle unterschiedlich.

So können Sie 0 erhalten.

Erweiterung: tatsächlich erhalten Sie Null für Null ... Entschuldigung, der Beweis ist nützlicher, um zu zeigen, dass es nicht so einfach ist, wie es für den ersten Punkt scheint. Der wichtige Teil ist, dass Sie die Bits von c als eine boolesche Funktion der Bits von x ausdrücken können.

---

Es gibt ein anderes Problem mit diesem Zufallszahlengenerator. Und das ist, dass selbst wenn man irgendwie die Funktion nicht solches Problem hat ändern (zum Beispiel durch Zugabe von 1 in jeder Iteration):

1. Sie können immer noch nicht garantieren, dass es nicht in bekommen eine kurze Schleife * für alle möglichen Werte von x. Was ist, wenn es eine Schleife mit 5 Längen für den Wert 345234523452345 gibt? Können Sie für alle möglichen Ausgangswerte nachweisen? Ich kann nicht.

2. Eigentlich mit einer wirklich Pseudo-Zufalls-Iteration-Funktion, Ihr System wird wahrscheinlich Schleife nach 2^32 Iterationen. Es hat eine fast trivial combinatoric Grund hat, aber „leider dieser Spielraum ist klein, sie zu enthalten“ ;-)

So:

• Wenn ein 2^32 Schleifenlänge für Ihre PRNG ist in Ordnung, dann verwenden eine bewährte Iterationsfunktion, die irgendwo im Netz gesammelt wurde.
• Wenn dies nicht der Fall ist, aktualisieren Sie die Bitlänge auf mindestens 2^128. Es wird eine etwa 2^64 Loop-Länge ergeben, die nicht so schlecht ist.
• Wenn Sie weiterhin eine 64-Bit-Ausgabe wünschen, verwenden Sie intern 128-Bit-Zahlen, aber geben Sie (x>>64)^(x&(2^64-1)) zurück (d. H. Xor-in die obere und untere Hälfte des internen Status x).

Answer 2

Kurze Antwort: Nein, es kann keine Null zurückgeben.

Nach der Numeric Recipes "es produziert eine volle Periode von 2^64-1 [...] der fehlende Wert ist Null".

Das Wesentliche ist, dass diese Verschiebungswerte sorgfältig ausgewählt wurden, um sehr lange Sequenzen zu machen (maximal möglich ohne Null) und somit kann man sicher sein, dass jede Zahl produziert wird. Null ist in der Tat der Fixpunkt dieses Generators, daher erzeugt er 2 Sequenzen: Null und die andere enthält jede andere Zahl.

Also IMO für einen ausreichend kleinen Bereich max-min es ist genug, um eine Funktion (next() - 1) % (max - min) + min machen oder sogar die Subtraktion ganz weglassen als Null wird von der Modulo zurückgegeben werden. Wenn man eine bessere Qualität gleichmäßige Verteilung will, sollte man die ‚üblichen‘ Methode von next() als Basisgenerator mit einer Reihe von [1, 2^64)