Sebuah jawaban terbaru menyebutkan penggunaan Fortuna atau Mersenne Twister Random Number Generator ( RNGs ) untuk menabur simulasi Monte Carlo . Saya belum pernah mendengar Fortuna sebelumnya jadi saya mencarinya - sepertinya ini terutama ditujukan untuk penggunaan kriptografi.
Saat ini saya menggunakan Mersenne Twister dalam kode produksi untuk menyemai algoritma K-Means.
Yang mana (Fortuna atau Mersenne Twister) yang dianggap terbaik untuk aplikasi "seeding seeding" (mis. Seeding Monte Carlo dan K-Means)? Atau apakah itu "melemparkan" - yaitu menggunakan yang paling nyaman.
Dari tempat saya duduk, "terbaik" harus memberikan angka acak kualitas tertinggi, beroperasi dengan cepat, dan (mungkin) memiliki jejak memori yang rendah. Dari semua ini, kualitas mungkin yang paling penting bagi kebanyakan dari kita.
RAND_MAX=32768nilai yang mungkin. Saat ini saya menggunakan MT untuk sim Monte Carlo raytracing. Namun, saya tidak melihat MT sebagai hambatan kinerja di profiler saya, mungkin karena saya melakukan generasi "acak" hal-hal seperti arah ray sebagai preprocess . Sebagai contoh, saya mungkin menghasilkan array 100.000 sinar saat startup, menyimpannya dalam sebuah array, dan secara acak memilih posisi awal array saat runtime (berjalan untuk 10.000 sinar atau lebih dari koleksi). Ini memiliki overhead memori yang relatif tinggi, dengan imbalan distribusi angka acak yang baik.Jawaban:
Ya, semuanya merupakan pertukaran atau semacamnya. Untuk generator angka acak, saya mengelompokkannya ke dalam 3 kategori dasar:
PRNGs kongruensi linier (metode yang umumnya diterapkan di sebagian besar perpustakaan) secara solid berada dalam kategori 1. Baik Fortuna dan Mersenne Twister berada dalam kategori 2.
Untuk artikel yang menarik tentang bagaimana mengacaukan algoritma pengocokan dapat membebani perusahaan / kasino Anda, saya sarankan yang ini dari tahun 1999 . Karena tautan busuk, gambarnya hilang, tetapi gambar 4, gambar tempat Anda memplot nomor berikutnya dari PRNG dengan angka sebelumnya yang dihasilkan, adalah serangkaian garis paralel.
Seperti yang ditunjukkan JM, Fortuna lambat. Seperti yang telah Anda tunjukkan, Mersenne Twister cukup cepat.
sumber
Pilihan default dalam kategori "kriptografi" adalah Blum-Blum-Shub , saya pikir. Seperti yang dikatakan halaman wikipedia, ini tidak cocok untuk simulasi karena terlalu lambat.
Jika Anda menggunakan sistem unix-like, maka Anda juga dapat mempertimbangkan untuk mendapatkan nomor acak langsung dari / dev / urandom , layanan sistem operasi yang menyediakan nomor acak berkualitas baik (walaupun tidak harus crypto). Bergantung pada OS tertentu yang Anda gunakan, ini dapat menggunakan algoritma Yarrow - yang merupakan varian dari Fortuna. Tetapi aspek yang paling menarik adalah bahwa sistem operasi memiliki akses ke beberapa angka acak yang benar: noise termal dari sensor suhu internal, misalnya. Biasanya, data ini dicampur ke dalam kumpulan acak setiap kali tersedia untuk menjaga data tidak dapat diprediksi.
Konsep pencampuran ini secara acak menunjukkan bahwa dimungkinkan untuk mendapatkan yang terbaik dari kedua dunia sebagai berikut. Gunakan generator nomor acak yang lebih cepat dan berkualitas baik seperti Mersenne sebagai RNG dasar Anda. Mempertahankan generator nomor acak kedua yang lebih baik dan berkualitas - misalnya Fortuna. Setiap begitu banyak angka, katakanlah 25, jalankan satu iterasi dari RNG yang lebih baik dan tambahkan hasilnya ke dalam status RNG dasar Anda. Dengan cara ini Anda akan mendapatkan kinerja yang cukup tinggi dan hasil berkualitas cukup tinggi. (Saya kira itu akan sia-sia untuk crypto, karena kekuatan generator komposit ini mungkin kekuatan dari tautan terlemah. Tetapi untuk simulasi, di mana Anda biasanya tidak memiliki musuh jahat, itu mungkin berhasil.)
sumber
Saya ingin mengatakan bahwa, saya baru saja melewati proses ini dengan simulasi dan saya harus mencatat bahwa menggunakan Fortuna tidak keluar dari pertanyaan jika itu benar-benar diperlukan. Dalam kasus kami, kami khawatir bahwa entropi MT tidak cukup tinggi yang akan menerjemahkan dalam simulasi kami menjadi bias. Jadi untuk simulasi kami, kami menggunakan Fortuna menarik sekitar 65 miliar angka acak dari algo itu. Intinya, komputer cepat, jika Anda benar-benar perlu, Anda dapat menggunakannya jika Anda punya alasan. Jika Anda hanya melakukan sesuatu seperti integrasi monte carlo, tetap dengan MT.
sumber
Saya pikir jawabannya sangat tergantung pada aplikasi yang Anda inginkan agar RNG dapat digunakan. Saya menyarankan kategori keempat untuk klasifikasi kasar Tangurena: "Bagus tanpa keuntungan nyata".
Untuk banyak aplikasi, itu mungkin tidak masalah, dan RNG tingkat kriptografi yang tepat dapat memperlambat tugas Anda tanpa mendapatkan validitas yang sepadan. Sebagai contoh, banyak dari penelitian yang saya lakukan hanya memerlukan banyak, jutaan angka yang berasal dari distribusi yang saya tentukan. Hampir semua RNG akan melakukannya, jadi yang saya butuhkan adalah yang tidak begitu miskin sehingga tidak berharga sebagai RNG. Hal lain hanya memperlambat pekerjaan yang tidak perlu. Saya cenderung menggunakan Mersenne Twister, tapi itu hanya karena itu berfungsi dengan cukup baik, saya punya kodenya, dan itu cukup cepat.
sumber