Bagaimana saya bisa menentukan periode generator nomor pseudo-acak saya?

14

Misalkan saya menggunakan generator nomor semu kongruen-acak (PRNG). Diberikan seed , faktor pengali (a), faktor shift (c) dan faktor modulus (m), bagaimana saya bisa menentukan periode PRNG saya? Apakah saya menentukannya dengan eksperimen / algoritma deteksi pola, atau adakah formula langsung untuk menghitung periodenya? x0

Meskipun pertanyaan saya secara khusus tentang metode linear kongruensial, saya terbuka untuk mengetahui lebih banyak tentang bagaimana periode dihitung dalam praktek untuk PRNG lain juga.

random-number-generation Paul
sumber
Relevan: en.wikipedia.org/wiki/…
BTW, jika Anda menggunakan LFSR maka periode adalah maksimal jika umpan balik polinomial primitif . Dalam kasus seperti itu, periode AFAIK (jangan mengutip saya; terlalu malas untuk menggali catatan kursus saya) adalah mana umpan balik polinomial p ( x ) ∈ F q [ x ] dari derajat n , dan qqnp(x)∈Fq[x]nq adalah ukuran dari bidang koefisien.
2
Algoritma pendeteksi siklus Floyd serta algoritma pendeteksian siklus Brent adalah cara yang efisien untuk mendeteksi siklus. Keduanya akan mengembalikan beberapa L dari periode, dan setelah Anda memilikinya, Anda dapat membuat faktor L dan melihat mana faktor terkecil yang merupakan suatu periode.
xdavidliu

Jawaban:

12

Jika Anda membatasi diri Anda untuk siklus penuh LCG PRNG maka jawabannya mudah, menurut definisi itu hanya m .

Untuk menemukan periode non-siklus LCG PRNG untuk benih yang diberikan Anda hanya perlu menghitung jumlah iterasi dari PRNG sampai menghasilkan nilai benih sekali lagi.

Dari halaman wikipedia yang dirujuk :

Panjang periode

The periode dari LCG umum paling m , dan untuk beberapa pilihan yang jauh lebih sedikit dari itu. Asalkan c bukan nol, LCG akan memiliki periode penuh untuk semua nilai seed jika dan hanya jika :

  • c danm yangrelatif prima,
  • Sebuah-1 habis dibagi oleh semuafaktor primadarim
  • Sebuah-1 adalah kelipatan dari 4 jikam adalah kelipatan dari 4.

Sementara LCGs mampu menghasilkan angka pseudorandom yang layak , ini sangat sensitif terhadap pilihan parameter c , m , dan Sebuah .

Secara historis, pilihan yang buruk telah menyebabkan implementasi LCG yang tidak efektif. Contoh ilustratif dari hal ini adalah RANDU yang banyak digunakan pada awal 1970-an dan membawa banyak hasil yang saat ini sedang dipertanyakan karena penggunaan LCG yang buruk ini.

Mengapa Anda ingin menggunakan generator siklus penuh

Jika Anda tidak membatasi diri untuk siklus penuh LCG PRNG maka Anda mengambil risiko besar .

Jika kamu tidak tahu bahwa LCG yang diberikan adalah siklus penuh maka Anda bisa berakhir dengan generator dengan jumlah urutan berbeda yang sewenang-wenang, beberapa di antaranya bisa sangat memalukan dan memiliki keacakan yang mengerikan, bahkan mungkin lebih buruk daripada generator RANDU yang terkenal itu. .

Anda benar-benar tidak ingin harus memeriksa setiap nilai seed yang mungkin untuk memastikan bahwa ia menghasilkan urutan yang cukup lama untuk aplikasi Anda.

Bacaan lebih lanjut

Untuk primer yang sangat baik pada generator angka acak pseudo, saya akan sangat menyarankan Anda membaca bab Resep Numerik pada Angka Acak.

Mark Booth
sumber
Itu benar, tapi saya tidak membatasi diri untuk periode penuh LCG PRNG ... Saya ingin tahu tentang pilihan yang buruk dari a, c, dan m, sehingga aliran acak yang tidak mencapai periode penuh. Saya ingin dapat mengetahui sebelumnya, mengingat beberapa a, c, dan m, seperti apa periode itu. Saya tahu bahwa itu dibatasi oleh m, tapi saya bertanya-tanya apakah kita bisa melakukan lebih baik dari itu dan mendapatkan periode yang tepat.
Paul
Saya tidak berpikir ini memecah rambut pada teknis sama sekali: pertanyaannya adalah "bagaimana menentukan periode LCG dengan parameter sewenang-wenang", sedangkan jawaban ini mengatakan "jangan gunakan LCG sewenang-wenang, selalu gunakan LCG periode penuh, dan dengan asumsi Anda lakukan , jawaban atas pertanyaan Anda adalah periode maksimum yang mungkin, menurut definisi ". Argumen untuk menggunakan LCF periode penuh yang dijabarkan dalam jawaban ini sangat meyakinkan, tapi masalahnya bukan itu yang ditanyakan.
xdavidliu
Maaf @xdavidliu tetapi saya tidak melihat bagaimana komentar baru Anda membantu saya meningkatkan jawaban saya. Anda menarik perhatian saya bahwa saya tidak benar-benar menjawab pertanyaan, saya mengedit jawaban saya untuk memperbaikinya, dan kemudian memberi tahu Anda dengan cara yang saya pikir dapat membuat Anda tersenyum (jika Anda adalah penggemar Futurama). Saya tidak melihat apa-apa lagi yang perlu dikatakan.
Mark Booth
Perhatikan bahwa pada pertukaran tumpukan, komentar tidak dimaksudkan untuk diskusi panjang, untuk itu gunakan Obrolan Ilmu Komputasi . Komentar adalah untuk membantu meningkatkan pertanyaan dan jawaban, dan mengganggu, jadi kami mencoba untuk menjaga seminimal mungkin. Komentar harus dianggap sementara, komentar apa pun yang tidak lagi aktif membantu meningkatkan pertanyaan atau jawaban dapat dihapus kapan saja untuk merapikan posting.
Mark Booth