Mengapa Mersenne Twister dianggap baik?

Mersenne Twister secara luas dianggap baik. Heck, sumber CPython mengatakan bahwa itu "adalah salah satu generator paling banyak diuji yang ada." Tapi apa artinya ini? Saat ditanya daftar properti generator ini, sebagian besar yang dapat saya tawarkan adalah buruk:

• Ini sangat besar dan tidak fleksibel (mis. Tidak mencari atau beberapa aliran),
• Itu gagal tes statistik standar meskipun ukuran negara besar,
• Ini memiliki masalah serius di sekitar 0, menunjukkan bahwa itu mengacak dirinya sendiri dengan buruk,
• Ini tidak cepat

dan seterusnya. Dibandingkan dengan RNG sederhana seperti XorShift *, ini juga sangat rumit.

Jadi saya mencari beberapa informasi tentang mengapa ini dianggap baik. Makalah asli membuat banyak komentar pada periode "super astronomi" dan pemerataan distribusi 623 dimensi, kata

Di antara banyak langkah yang diketahui, tes berdasarkan keseragaman dimensi yang lebih tinggi, seperti tes spektral (lih, Knuth [1981]) dan uji distribusi k, yang dijelaskan di bawah ini, dianggap paling kuat.

Tapi, untuk properti ini, generator dikalahkan oleh penghitung yang cukup panjang! Ini tidak membuat komentar tentang distribusi lokal , yang sebenarnya Anda pedulikan dalam generator (meskipun "lokal" dapat berarti berbagai hal). Dan bahkan CSPRNG tidak peduli untuk periode besar seperti itu, karena itu tidak terlalu penting.

Ada banyak matematika di koran, tetapi sejauh yang saya tahu sedikit ini sebenarnya tentang kualitas keacakan. Hampir setiap penyebutan dengan cepat melompat kembali ke klaim asli, sebagian besar tidak berguna ini.

Sepertinya orang melompat ke kereta musik ini dengan mengorbankan teknologi yang lebih tua dan lebih dapat diandalkan. Misalnya, jika Anda hanya menambah jumlah kata dalam LCG menjadi 3 (jauh lebih sedikit daripada "hanya 624" dari Mersenne Twister) dan menampilkan kata teratas setiap pass, ia melewati BigCrush ( bagian yang lebih sulit dari TestU01 test suite ), meskipun Twister gagal ( kertas PCG, gbr. 2 ). Mengingat ini, dan bukti-bukti yang lemah saya bisa menemukan mendukung Mersenne Twister, apa yang lakukan menyebabkan perhatian untuk mendukung itu atas pilihan lain?

Ini juga bukan murni sejarah. Saya telah diberitahu secara sepintas bahwa Mersenne Twister setidaknya lebih terbukti dalam praktik daripada, katakanlah, PCG acak . Tetapi apakah penggunaan case sangat cerdas sehingga mereka bisa melakukan lebih baik daripada baterai tes kami? Beberapa Googling menyarankan mereka mungkin tidak.

Singkatnya, saya bertanya-tanya bagaimana Mersenne Twister mendapatkan reputasi positif luasnya, baik dalam konteks historisnya maupun sebaliknya. Di satu sisi saya jelas skeptis terhadap kualitasnya, tetapi di sisi lain sulit membayangkan bahwa itu adalah kejadian yang sepenuhnya acak.

MT dianggap baik selama beberapa tahun, sampai ternyata sangat buruk dengan tes BigCrush TestU01 yang lebih maju dan PRNG yang lebih baik.

Tabel di pcg-random.org misalnya memberikan gambaran yang baik tentang fitur dari beberapa PRNG yang paling banyak digunakan, di mana satu-satunya fitur "baik" dari Mersenne Twister adalah periode yang sangat besar, $2^{219937}$ dan kemungkinan untuk menggunakan sebuah seed (Reproducible Hasil), ia lulus tes SmallCrush TestU01 sederhana dan cepat, tetapi gagal beberapa tes kualitas statistik yang lebih baru, esp. Uji LinearComp TestU01 dan Baterai Crush dan BigCrush TestU01.

Halaman ini mencantumkan fitur Mersenne-Twister secara rinci:

Kualitas Positif

• Menghasilkan angka 32-bit atau 64-bit (dengan demikian dapat digunakan sebagai sumber bit acak)
• Lulus sebagian besar tes statistik

Kualitas Netral

• Periode luar biasa besar $2^{219937} - 1$
• Didistribusikan secara berdimensi 623
• Periode dapat dipartisi untuk meniru beberapa aliran

Kualitas Negatif

• Gagal beberapa uji statistik, dengan sedikitnya 45.000 angka.
• Dapat diprediksi - setelah 624 keluaran, kami dapat sepenuhnya memprediksi keluarannya.
• Status generator menempati 2504 byte RAM - sebaliknya, generator yang sangat dapat digunakan dengan periode lebih keras daripada siapa pun dapat menggunakan bisa muat dalam 8 byte RAM.
• Tidak terlalu cepat.
• $2^{219937}$
• Outputnya tidak merata; generator bisa masuk ke "kondisi buruk" yang lambat untuk pulih.
• Penyemaian yang hanya berbeda sedikit membutuhkan waktu lama untuk berbeda satu sama lain; pembenihan harus dilakukan dengan hati-hati untuk menghindari keadaan buruk.
• Meskipun lompatan ke depan dimungkinkan, algoritma untuk melakukannya lambat untuk dikomputasi (yaitu, membutuhkan beberapa detik) dan jarang disediakan oleh implementasi.

Rangkuman : Mersenne Twister tidak lagi cukup bagus, tetapi sebagian besar aplikasi dan perpustakaan belum ada di sana.

Saya Editor yang menerima makalah MT di ACM TOMS pada tahun 1998 dan saya juga desainer TestU01. Saya tidak menggunakan MT, tetapi kebanyakan MRG32k3a, MRG31k3p, dan LRSR113. Untuk mengetahui lebih banyak tentang ini, tentang MT, dan tentang apa lagi yang ada, Anda dapat melihat makalah-makalah berikut:

F. Panneton, P. L'Ecuyer, dan M. Matsumoto, `` Peningkatan Generator Jangka Panjang Berdasarkan Linear Recurrences Modulo 2 '', Transaksi ACM pada Perangkat Lunak Matematika, 32, 1 (2006), 1-16.

P. L'Ecuyer, `` Generasi Angka Acak '', bab 3 dari Buku Pegangan Statistik Komputasi, JE Gentle, W. Haerdle, dan Y. Mori, eds., Edisi Kedua, Springer-Verlag, 2012, 35-71 . https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3

P. L'Ecuyer, D. Munger, B. Oreshkin, dan R. Simard, `` Nomor Acak untuk Komputer Paralel: Persyaratan dan Metode, '' Matematika dan Komputer dalam Simulasi, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, `` Generasi Nomor Acak dengan Berbagai Aliran untuk Komputer Berurutan dan Paralel, '' mengundang tutorial lanjutan, Prosiding Konferensi Simulasi Musim Dingin 2015, IEEE Press, 2015, 31-44.

Agak seperti pengurutan algoritma dalam hal ini, tidak ada "satu ukuran cocok untuk semua" PRNG. Yang berbeda digunakan untuk tujuan yang berbeda dan ada berbagai kriteria dan kegunaan desain. Dimungkinkan untuk menyalahgunakan PRNG, seperti menggunakan satu untuk kriptografi yang tidak dirancang untuknya. Entri Wikipedia tentang Mersenne Twister juga menyebutkan bahwa itu tidak dirancang untuk "simulasi Monte-Carlo yang memerlukan generator nomor acak independen".

Sebagaimana dicatat di Wikipedia, PRNG ini memang digunakan dalam sejumlah besar bahasa pemrograman dan aplikasi bahkan sebagai PRNG default. Diperlukan analisis sosiologis dekat untuk menjelaskan mengapa satu PRNG disukai. Beberapa faktor yang mungkin berkontribusi pada PRNG ini:

• Penulis memiliki kredensial ilmiah yang baik / kuat di bidangnya dan telah bekerja di PRNG selama beberapa dekade.

• Itu secara khusus dirancang untuk menjadi lebih unggul daripada metode lain pada saat itu.

• Penulis terlibat dalam implementasi dan pelacakan mereka, juga berkontribusi pada mereka. Beberapa PRNG lebih teoretis dan penulis tidak selalu mementingkan diri sendiri dengan implementasi yang sebenarnya.

• Sistem didukung / diperbarui dengan baik pada halaman web.

• Versi baru PRNG telah dikembangkan untuk mengatasi kelemahan. Tidak ada satu algoritma tunggal Mersenne Twister, lebih seperti versi yang berbeda dan keluarga varian yang dapat menangani kebutuhan yang berbeda.

• Telah dianalisis / diuji secara luas oleh perangkat lunak analisis keacakan standar dan disahkan, oleh otoritas independen.

• Ada efek yang diketahui diukur dengan untuk situs web dan banyak konteks lain seperti kutipan ilmiah yang disebut "lampiran preferensial" yang dapat diukur. Itu pada dasarnya di mana sumber-sumber sejarah yang lama didirikan menambah penggunaan lebih lanjut. Efek seperti itu dapat menjelaskan pilihan PRNG dari waktu ke waktu.

Dengan kata lain, Anda bertanya tentang fenomena "popularitas" yang dikaitkan dan saling terkait dengan pilihan manusia dan tidak terikat erat dengan kualitas tertentu, tetapi merupakan jenis properti yang kompleks / muncul dan saling mempengaruhi antara berbagai algoritma, pengguna, dan lingkungan. / konteks penggunaan.

Berikut adalah salah satu analisis independen dari algoritma Mersenne Twister - A Pseudo Random Number Generator dan Variannya oleh Jagannatam (15p). Paragraf penutup pada dasarnya adalah jawaban untuk pertanyaan Anda. mengutip hanya 1 ^st beberapa kalimat:

Mersenne Twister secara teoritis terbukti sebagai PRNG yang baik, dengan periode panjang dan pemerataan yang tinggi. Ini banyak digunakan di bidang simulasi dan modulasi. Cacat yang ditemukan oleh pengguna telah diperbaiki oleh penemu. MT telah ditingkatkan, untuk digunakan dan agar kompatibel dengan teknologi CPU yang baru muncul seperti SIMD dan pipa paralel dalam versi SFMT-nya.