GUT Pseudozufallszahlengenerationen

Ich habe MT19937in einem Test-Harness einheitliche (vorzeichenlose) 32-Bit- Werte [0, - 1] basierend auf der ursprünglichen mt19937.c- Implementierung der Autoren generiert , um ein (im Wesentlichen unerschöpfliches) Angebot an zu generieren statistisch zufälliger Strom von Bitoktetten. Dies ersetzt ein CSPRNG, das für diese speziellen Tests nicht erforderlich ist. Ich habe jedoch kürzlich über die PRNGs nachgedacht - nicht wegen der statistischen Eigenschaften als solche (beide scheinen für meine Bedürfnisse mehr als angemessen zu sein) -, aber sie scheinen eine effizientere Implementierung vorzuschlagen. $2^{32}$ WELL

Mir fehlt der mathematische Hintergrund für die wissenschaftlichen Arbeiten, obwohl ich zumindest der 'Twist'-Matrix und der Tempering-Transformation für die erstere folgen könnte. Ein Großteil des von den Autoren der WELL-nFunktionen bereitgestellten Codes scheint sich jedoch auf die Gleitkommaerzeugung mit einigen magischen Gleitkommakonstanten (z 2.32830643653869628906e-10. B. ) zu konzentrieren. Können Schritte im WELLCode weggelassen werden, um eine einheitliche 32-Bit-Verteilung bereitzustellen? Oder ist der Algorithmus speziell für Gleitkommaverteilungen entwickelt / voreingenommen?

Oder ich bin ein falscher WELLDenker, der einen Leistungsgewinn für die Erzeugung von "Bulk" -Uint32-Vektoren bringt und gleichzeitig meine Anforderungen erfüllt?

performance c random-number-generation Brett Hale
quelle

Wenn dies nur Neugier ist, ist das in Ordnung, aber die tatsächliche Leistung hängt immer davon ab, was sonst noch vor sich geht. Wenn das Generieren von Zufallszahlen 10% der Gesamtzeit in Anspruch nimmt und Sie es um die Hälfte reduzieren können, erhalten Sie eine Beschleunigung von 5%, was die Mühe möglicherweise nicht wert ist.

Mike Dunlavey

Vielleicht nicht zum Thema gehörend, aber es lohnt sich auch, Generatoren für den Gegenmodus wie deshawresearch.com/resources_random123.html in Betracht zu ziehen , die viel, viel weniger Speicher benötigen und trivial parallelisieren.

Geoffrey Irving

Als Update PCGneige ich mich jetzt zu den RNGs. Sie sind viel schneller, können sehr lange Zeiträume (sowie mehrere Ströme) mit statistisch hervorragenden Eigenschaften versorgen und scheinen sich sehr schnell von schlechten IVs zu erholen.

Brett Hale

Antworten:

Ich würde mir vorstellen, dass die meisten Benutzer von Zufallszahlengeneratoren letztendlich an Gleitkommawerten interessiert sind. Aus diesem Grund gibt es den SIMD-orientierten Fast Mersenne Twister (dSFMT) mit doppelter Genauigkeit . Es gibt jedoch einen neueren C-Code für das WELL RNG , der unsigned longWerte zurückgibt . Wenn Sie sich den Code ansehen, scheint es, dass die frühere Version verwendet wurde unsigned long, doublesodass Sie möglicherweise herausfinden können, was sie getan haben, indem Sie die beiden vergleichen.

Wenn Sie sich hauptsächlich für Geschwindigkeit interessieren, denke ich nicht, dass dies das PRNG für Sie ist. Die Geschwindigkeit / Leistung, auf die sich die Autoren beziehen, ist nicht, wie schnell der Algorithmus zufällige Variationen generiert, sondern wie schnell er sich von einer schlechten Initialisierung erholt . Dies verbessert die statistischen Eigenschaften des WELL-Generators. Einzelheiten dazu finden Sie in Abschnitt 6 der Masterarbeit von Mutsuo Saito (PDF). Solche Tests werden mit künstlichen Worst-Case-Anfangszuständen durchgeführt, daher ist mir unklar, wie sich der Effekt im Allgemeinen auswirkt.

Die Generierung von Zufallszahlen kann - oft trotz der eigenen Intuition - recht teuer sein und ist ein sehr guter Kandidat für die Optimierung, vorausgesetzt, Ihr Code verbringt eine angemessene Zeit damit, zufällige Werte zu erstellen. In meinen eigenen einfachen Leistungstests (Retina MacBook Pro, OS X 10.9) stellte ich fest, dass das WELL RNG bei der Erstellung von Werten etwa ein Drittel so schnell ist wie der derzeitige ganzzahlige SIMD-orientierte Fast Mersenne Twister (SFMT) uint32. SFMThat auch Unterstützung für uint64. Ich fand auch, dass der klassische mt19937ar.cCode ungefähr halb so schnell ist wie SFMT.

Horchler
quelle