Algoritma pembangkitan angka semu-acak

12

Algoritma apa yang digunakan dalam generator angka acak modern dan berkualitas baik?

Mehper C. Palavuzlar
sumber
1
Retagged "random-variate" ke "random-variable" untuk konsistensi dengan pertanyaan serupa.
Whuber

Jawaban:

10

Dalam R, pengaturan default untuk pembuatan angka acak adalah:

  1. Untuk U (0,1), gunakan algoritma Mersenne-Twister
  2. Untuk nomor Guassian gunakan inversi numerik dari fungsi distribusi normal standar.

Anda dapat dengan mudah memeriksa ini, yaitu.

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

Dimungkinkan untuk mengubah generator default ke PRNG lain, seperti Super-Duper, Wichmann-Hill, Marsaglia-Multicarry atau bahkan PRNG yang disediakan pengguna. Lihat? RNGkind untuk perincian lebih lanjut. Saya tidak pernah perlu mengubah PRNG default.

The C GSL perpustakaan juga menggunakan Mersenne-Twister secara default.

csgillespie
sumber
Apakah Anda yakin tentang poin kedua Anda, menghasilkan variabel acak normal dengan membalikkan CDF? Kebalikan dari CDF normal adalah fungsi yang cukup mahal untuk dievaluasi. Saya membayangkan metode Box-Muller akan lebih cepat. Masih lebih cepat akan menjadi metode ziggurat Marsaglia untuk menghasilkan normals.
John D. Cook
Saya juga menemukan ini mencurigakan. Zaggurat Marsaglia adalah default di Matlab, dan saya tidak bisa membayangkan Matlab lebih baik daripada R di bidang generasi nomor acak.
shabbychef
@ John Memang, metode kutub tersedia di R, lihat paket setRNG.
chl
3

Xorshift PNG dirancang oleh George Marsaglia. Periode ini (2 ^ 128-1) jauh lebih pendek daripada Mersenne-Twister tetapi algoritma ini sangat sederhana untuk diimplementasikan dan cocok untuk paralelisasi. Berkinerja baik pada banyak arsitektur inti seperti chip DSP dan Tesla Nvidia.

brotchie
sumber
Apakah ini baik untuk diterapkan pada GPU? Tautan ke detail, referensi?
DarenW
2
Thomas, Howes, Luk - 2009 - Perbandingan CPU, GPU, FPGA, dan array prosesor paralel besar-besaran untuk pembuatan angka acak. doi.acm.org/10.1145/1508128.1508139 . Diskusi + tolok ukur dari serangkaian PNG yang mengeksekusi pada CPU, GPU, FPGA, dan Array Prosesor Paralel Masif.
brotchie
Mungkin juga RNG L'Ecuyer's dengan beberapa aliran ( j.mp/bzJSlm )?
chl
3

Di http://prng.di.unimi.it/ Anda dapat menemukan baku tembak beberapa generator bilangan acak yang diuji menggunakan TestU01, rangkaian uji modern untuk generator bilangan pseudorandom yang menggantikan diehard dan dieharder. Anda dapat memilih.

seba
sumber