Wie gut ist java.util.Random?

Question

Zwei Fragen:

Werde ich für jedes Saatgut, das ich einsetze, eine andere Zahlenfolge erhalten?

Gibt es einige "tote" Samen? (Solche, die Nullen produzieren oder sich sehr schnell wiederholen.)

Welche anderen PRNGs sollte ich übrigens verwenden, wenn überhaupt?

Lösung: Da ich den PRNG für ein Spiel verwenden werde, muss er nicht kryptografisch sicher sein. Ich entscheide mich für den Mersenne-Twister, sowohl wegen seiner Geschwindigkeit als auch wegen seines großen Zeitraums.

Answer 1

In gewissem Maße sind Zufallszahlengeneratoren Pferde für Kurse. Die Klasse Random implementiert einen LCG mit vernünftig gewählten Parametern. Dennoch weist sie die folgenden Merkmale auf:

• relativ kurzer Zeitraum (2^48)
• Bits nicht gleichermaßen zufällig sind (siehe meinen Artikel über Zufälligkeit der Bitpositionen )
• wird nur einen kleinen Teil der Kombinationen von Werten (das berühmte Problem der " in die Flugzeuge fallen ")

Wenn diese Dinge für Sie keine Rolle spielen, dann hat Random den Vorteil, dass es als Teil des JDK bereitgestellt wird. Es ist gut genug für gelegentliche Spiele (aber nicht für solche, bei denen es um Geld geht). Es gibt keine schwachen Samen als solche.

Eine weitere Alternative ist die XORShift-Generator die in Java wie folgt implementiert werden kann:

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

Für einige sehr billige Operationen hat dies eine Periode von 2^64-1 (Null ist nicht erlaubt), und ist einfach genug, um inlined zu werden, wenn Sie Werte wiederholt erzeugen. Es sind verschiedene Verschiebungswerte möglich: siehe George Marsaglias Arbeit über XORShift-Generatoren für weitere Details. Sie können die Bits in den erzeugten Zahlen als gleichermaßen zufällig betrachten. Eine Hauptschwäche ist, dass es gelegentlich in einen "Trott" gerät, bei dem nicht viele Bits in der Zahl gesetzt sind, und dann dauert es ein paar Generationen, um aus diesem Trott herauszukommen.

Andere Möglichkeiten sind:

• Kombination verschiedener Generatoren (z. B. Einspeisung der Ausgabe eines XORShift-Generators in einen LCG und anschließende Addition des Ergebnisses mit der Ausgabe eines XORShift-Generators mit anderen Parametern): Auf diese Weise können im Allgemeinen die Schwächen der verschiedenen Methoden "geglättet" werden, und es kann eine längere Periode erzielt werden, wenn die Perioden der kombinierten Generatoren sorgfältig gewählt werden
• eine "Verzögerung" hinzufügen (um einen längeren Zeitraum zu erhalten): Im Wesentlichen wird an der Stelle, an der ein Generator normalerweise die zuletzt erzeugte Zahl umwandeln würde, ein "Historienpuffer" gespeichert und z. B. die (n-1023)-te umgewandelt.

Ich würde sagen, vermeiden Sie Generatoren, die eine dumme Menge an Speicher verwenden, um Ihnen eine längere Periode zu geben, als Sie wirklich brauchen (einige haben eine Periode, die größer ist als die Anzahl der Atome im Universum - das brauchen Sie normalerweise nicht). Und beachten Sie, dass "lange Periode" nicht unbedingt "qualitativ hochwertiger Generator" bedeutet (obwohl 2^48 immer noch ein bisschen wenig ist!).

Answer 2

Wie zvrba schon sagte, erklärt die JavaDoc die normale Implementierung. Die Wikipedia-Seite über Pseudo-Zufallszahlengeneratoren enthält eine ganze Reihe von Informationen und erwähnt die Mersenne-Twister das zwar nicht als kryptographisch sicher gilt, aber sehr schnell ist und über verschiedene Implementierungen in Java . (Der letzte Link enthält zwei Implementierungen - ich glaube, es gibt noch weitere).

Wenn Sie eine kryptografisch sichere Generierung benötigen, lesen Sie die Wikipedia-Seite - es gibt verschiedene Optionen.

Answer 3

Für RNGs ist die Implementierung von Sun definitiv nicht auf dem neuesten Stand der Technik aber für die meisten Zwecke ist es gut genug. Wenn Sie Zufallszahlen für kryptografische Zwecke benötigen, gibt es java.security.SecureRandom Wenn Sie einfach nur etwas Schnelleres und Besseres als java.util.random wollen, finden Sie im Netz leicht Java-Implementierungen des Mersenne Twisters.

Answer 4

Dies wird beschrieben in der Dokumentation . Lineare kongruente Generatoren sind theoretisch gut verstanden, und in der Literatur und im Internet ist eine Menge Material über sie verfügbar. Ein linearer kongruenter Generator mit gleichen Parametern gibt immer die gleiche periodische Folge aus, und das einzige, was der Seed bestimmt, ist, wo die Folge beginnt. Die Antwort auf Ihre erste Frage lautet also "ja, wenn Sie genügend Zufallszahlen erzeugen".

Answer 5

Siehe die Antwort in meinem Blogbeitrag:

http://code-o-matic.blogspot.com/2010/12/how-long-is-period-of-random-numbers.html

Random hat eine maximale Periode für seinen Zustand (eine lange, d.h. 2^64 Periode). Dies kann direkt auf 2^k verallgemeinert werden - investieren Sie so viele Zustandsbits wie Sie wollen, und Sie erhalten die maximale Periode. 2Mersenne Twister hat eigentlich eine sehr kurz Zeitraum (siehe die Kommentare im besagten Blogbeitrag).

-Oops. Random beschränkt sich auf 48 Bits, anstatt die vollen 64 Bits eines Longs zu verwenden, dementsprechend ist seine Periode 2^48, nicht 2^64.