Ist Fortuna oder Mersenne Twister als algorithmisches RNG vorzuziehen?

19

In einer kürzlichen Antwort wurde die Verwendung von Fortuna- oder Mersenne-Twister- Zufallszahlengeneratoren ( RNGs ) zur Erstellung einer Monte-Carlo-Simulation erwähnt . Ich hatte vorher noch nie von Fortuna gehört, also habe ich es nachgeschlagen - es scheint hauptsächlich für kryptografische Zwecke gedacht zu sein.

Ich verwende derzeit einen Mersenne Twister im Produktionscode, um einen K-Means-Algorithmus zu erstellen.

Welches (Fortuna oder Mersenne Twister) eignet sich am besten für "algorithmische Seeding" -Anwendungen (z. B. Seeding von Monte Carlo und K-Means)? Oder ist es ein "toss up" - dh am bequemsten zu benutzen.

Von meinem Platz aus sollte "best" Zufallszahlen von höchster Qualität liefern, schnell arbeiten und (möglicherweise) einen geringen Speicherbedarf haben. Qualität ist für die meisten von uns wahrscheinlich das Wichtigste.

winwaed
quelle
6
Kryptografische PRNGs sind in der Regel viel langsamer als die meisten anderen PRNGs. Wenn Sie eine Monte-Carlo-Simulation durchführen, bei der Ihre PRNG-Vorgänge im Millionenbereich liegen, werden Sie feststellen, dass kryptografische Methoden fürchterlich teuer sind.
JM
1
@JM - Mit ein bisschen mehr Detail denke ich, dass Ihr Kommentar als Antwort gut wäre. Es wäre sicherlich interessant zu prüfen, ob die moderne hardwarebeschleunigte Kryptofunktionalität verwendet werden könnte, um einen Hochleistungsstrom von kryptografisch sicheren Pseudozufallszahlen zu erzeugen.
Mark Booth
@JM guter Punkt, dass kryptografische RNGs langsam sind - gegen Fortuna
winwaed
heres eine gute Liste der PRNG ist und viele verschiedene Statistiken , dass Sie nützliche Hoffnung finden es hilft> boost.org/doc/libs/1_48_0/doc/html/boost_random/...
pyCthon
Mein Problem mit cstdlib war die Granularität - nur RAND_MAX=32768mögliche Werte. Ich benutze derzeit MT für Monte Carlo Raytracing Sim. Ich sehe MT jedoch nicht als Leistungsengpass in meinem Profiler, wahrscheinlich, weil ich Dinge wie Strahlrichtungen als Vorprozess "zufällig" generiere . Zum Beispiel könnte ich beim Start ein Array mit 100.000 Strahlen erzeugen, diese in einem Array speichern und zur Laufzeit zufällig die Startposition des Arrays auswählen (etwa 10.000 Strahlen der Sammlung). Dies hat einen relativ hohen Speicheraufwand im Austausch für gute Zufallszahlenverteilungen.
Bobobobo

Antworten:

14

Nun, alles ist ein Kompromiss. Für Zufallsgeneratoren gruppiere ich sie in drei grundlegende Kategorien:

  1. Gut genug für die Hausaufgaben.
  2. Gut genug, um auf Ihre Firma zu wetten.
  3. Gut genug, um auf dein Land zu wetten.

Lineare kongruente PRNGs (die Methode, die in den meisten Bibliotheken allgemein angewendet wird) gehören eindeutig zur Kategorie 1. Sowohl Fortuna als auch Mersenne Twister gehören eindeutig zur Kategorie 2.

Für einen interessanten Artikel darüber, wie durcheinander ein Mischalgorithmus Sie Ihre Firma / Ihr Casino kosten kann, empfehle ich diesen Artikel aus dem Jahr 1999 . Aufgrund von Link Rot sind die Bilder verschwunden, aber Abbildung 4, in der Sie die nächste Nummer aus dem PRNG gegen die zuvor erzeugte Nummer plotten, besteht aus einer Reihe paralleler Linien.

Wie JM betont, ist Fortuna langsam. Wie Sie bereits betont haben, ist Mersenne Twister recht schnell.

Tangurena
quelle
2
Schnell durch den Artikel von Skimming Druckversion „4“ erscheint Code statt eines Bildes zu sein. "Abbildung 5" sieht kaputt aus, aber dies ist das Bild, das ich von der WayBack-Maschine erhalten habe .
JM
Vielen Dank. sieht aus wie Geschwindigkeit ist ein Zeichen gegen Fortuna in diesem Fall. Re. Schlechtes Mischen: Ja, ich weiß genug (nicht viel!), Dass es einfach ist, die Zufälligkeit eines RNG "rückgängig zu machen" - zum Beispiel, indem man einen schlechten Startwert auswählt.
Winwaed
Eine andere Version mit besseren Bildern finden Sie unter: cigital.com/papers/download/developer_gambling.php
Tangurena
1
96-Bit-LCGs mit 32-Bit-Ausgängen bestehen mehr statistische Tests als Mersenne Twisters. Heutzutage sollte niemand mehr einen Mersenne Twister verwenden, da es so einfach ist, anständige nicht-kryptografische PRNGs zu erstellen, die in jeder Hinsicht weitaus besser sind als der MT.
Veedrac
4

Die Standardeinstellung in der Kategorie "kryptografisch" ist meiner Meinung nach Blum-Blum-Shub . Wie die Wikipedia-Seite bereits sagt, ist dies nicht für Simulationen geeignet, da es einfach zu langsam ist.

Wenn Sie auf einem Unix-ähnlichen System arbeiten, können Sie auch erwägen, Ihre Zufallszahlen direkt von / dev / urandom abzurufen , dem Betriebssystemdienst, der Zufallszahlen in guter (wenn auch nicht unbedingt in Krypto) Qualität bereitstellt. Je nach verwendetem Betriebssystem wird möglicherweise der Yarrow-Algorithmus verwendet, von dem Fortuna eine Variante ist. Der interessanteste Aspekt ist jedoch, dass das Betriebssystem Zugriff auf einige echte Zufallszahlen hat: z. B. thermisches Rauschen von internen Temperatursensoren. In der Regel werden diese Daten immer dann in den Zufallspool gemischt, wenn sie verfügbar sind, damit die Daten nicht vorhersehbar sind.

Dieses Konzept der Zufallsmischung legt nahe, dass es möglich sein könnte, das Beste aus beiden Welten wie folgt zu erzielen. Verwenden Sie einen schnelleren Zufallszahlengenerator guter Qualität wie Mersenne als Basis-RNG. Pflegen Sie auch einen zweiten Zufallszahlengenerator mit besserer Qualität - z. B. Fortuna. Alle so vielen Zahlen, sagen wir 25, führen eine Iteration des besseren RNG durch und addieren das Ergebnis in den Zustand Ihres Basis-RNG. Auf diese Weise erhalten Sie eine relativ hohe Leistung und Ergebnisse von relativ hoher Qualität. (Ich würde vermuten, dass es für Krypto nutzlos wäre, da die Stärke dieses zusammengesetzten Generators durchaus die Stärke des schwächsten Glieds sein könnte. In Simulationen, in denen Sie normalerweise keinen böswilligen Gegner haben, funktioniert es jedoch möglicherweise.)

Erik P.
quelle
/ dev / urandom ist sicher für die Verschlüsselung unter Linux und Free-BSD. Schauen Sie sich diese Antwort an
Adam Kurkiewicz
Warum ist es für Simulationen wünschenswert, dass Zufallszahlen wahr sind? Sicher, einige Pseudozufallszahlengeneratoren sind schlechter, andere sind jedoch für alle praktischen Zwecke ausreichend. Warum betrachten Sie Wahrhaftigkeit als eine gute Eigenschaft an sich?
Wrzlprmft
2

Ich wollte mich einschalten, um zu sagen, dass ich diesen Prozess kürzlich mit einer Simulation durchlaufen habe, und ich sollte beachten, dass die Verwendung von Fortuna nicht ausgeschlossen ist, wenn es wirklich notwendig ist. In unserem Fall befürchteten wir, dass die MT-Entropie nicht hoch genug ist, was sich in unserer Simulation in einer Verzerrung niederschlägt. Für unsere Simulation haben wir also Fortuna verwendet, um ungefähr 65 Milliarden Zufallszahlen aus diesem Algo zu ziehen. Computer sind schnell, wenn Sie es wirklich brauchen, können Sie sie verwenden, wenn Sie einen Grund haben. Wenn Sie nur so etwas wie eine Integration mit Monte Carlo machen, bleiben Sie bei MT.

tazz_ben
quelle
0

Ich denke, die Antwort hängt stark von der Anwendung ab, für die Sie das RNG verwenden möchten. Ich würde eine vierte Kategorie für Tangurenas grobe Klassifizierung vorschlagen: "Gut ohne wirklichen Gewinn".

Für viele Anwendungen spielt es möglicherweise keine Rolle, und ein ordnungsgemäß kryptografisch einwandfreies RNG kann Ihre Aufgaben verlangsamen, ohne dass dies zu einer entsprechenden Erhöhung der Gültigkeit führt. Zum Beispiel erfordert ein Großteil meiner Forschung nur viele, viele Millionen Zahlen, die ungefähr aus einer von mir angegebenen Verteilung stammen. Fast jedes RNG wird funktionieren, also brauche ich nur eines, das nicht so katastrophal arm ist, dass es als RNG wertlos ist . Alles andere verlangsamt die Arbeit nur unnötig. Ich benutze normalerweise Mersenne Twister, aber das liegt einfach daran, dass es gut genug funktioniert, ich habe den Code und es ist einigermaßen schnell.

Fomite
quelle