Algorithmen zur Erzeugung von Pseudozufallszahlen

12

Welche Algorithmen werden in modernen und qualitativ hochwertigen Zufallszahlengeneratoren verwendet?

algorithms random-variable random-generation Mehper C. Palavuzlar
quelle
1
Um die Übereinstimmung mit ähnlichen Fragen zu gewährleisten, wurde "random-variate" in "random-variable" umbenannt.
whuber

Antworten:

10

In R sind die Standardeinstellungen für die Zufallszahlengenerierung:

  1. Verwenden Sie für U (0,1) den Mersenne-Twister-Algorithmus
  2. Verwenden Sie für guassianische Zahlen die numerische Inversion der Standardnormalverteilungsfunktion.

Sie können dies leicht überprüfen, nämlich.

> RNGkind()
[1] "Mersenne-Twister" "Inversion"

Es ist möglich, den Standardgenerator auf andere PRNGs wie Super-Duper, Wichmann-Hill, Marsaglia-Multicarry oder sogar ein vom Benutzer bereitgestelltes PRNG umzustellen. Weitere Informationen finden Sie im RNGkind. Ich musste das Standard-PRNG nie ändern.

Die C GSL- Bibliothek verwendet standardmäßig auch den Mersenne-Twister .

csgillespie
quelle
Sind Sie sich über Ihren zweiten Punkt sicher, bei dem normale Zufallsvariablen durch Invertieren der CDF generiert werden? Die Umkehrung der normalen CDF ist eine ziemlich teure Funktion zur Bewertung. Ich stelle mir vor, Box-Mullers Methode wäre schneller. Noch schneller wäre Marsaglias Zikkurat-Methode zur Erzeugung von Normalen.
John D. Cook
Ich finde das auch verdächtig. Marsaglias Ziggurat ist die Standardeinstellung in Matlab, und ich kann mir nicht vorstellen, dass Matlab im Bereich der Zufallszahlengenerierung besser als R ist.
Shabbychef
@ John In der Tat ist die polare Methode in R verfügbar, siehe das setRNG-Paket.
Chl
3

Das von George Marsaglia entworfene Xorshift PNG. Seine Periode (2 ^ 128-1) ist viel kürzer als die des Mersenne-Twister, aber der Algorithmus ist sehr einfach zu implementieren und eignet sich für die Parallelisierung. Funktioniert gut auf vielen Kernarchitekturen wie DSP-Chips und Nvidias Tesla.

brotchie
quelle
Wäre dies gut für die Implementierung auf GPUs? Link zu Details, Referenzen?
DarenW
2
Thomas, Howes, Luk - 2009 - Ein Vergleich von CPUs, GPUs, FPGAs und massiv parallelen Prozessor-Arrays zur Erzeugung von Zufallszahlen. doi.acm.org/10.1145/1508128.1508139 . Diskussion + Benchmarks einer Reihe von PNGs, die auf CPU-, GPU-, FPGA- und Massively Parallel Processor Arrays ausgeführt werden.
Brotchie
Vielleicht auch L'Ecuyers RNG mit mehreren Streams ( j.mp/bzJSlm )?
Chl
3

Unter http://prng.di.unimi.it/ finden Sie eine Auswahl mehrerer Zufallszahlengeneratoren, die mit TestU01 getestet wurden, der modernen Testsuite für Pseudozufallszahlengeneratoren, die eingefleischte und dieharder ersetzten. Sie können auswählen und auswählen.

seba
quelle