Pertanyaan Mengapa linear_congruential_engine :: seed (Sseq) membuang tiga angka yang dihasilkan oleh urutan benih?


Standar C ++ (sepanjang jalan dari C ++ 11 ke C ++ 17 draft saat ini) mengatakan hal berikut di [rand.eng.lcong]:

template<class Sseq> explicit linear_congruential_engine(Sseq& q);

Efek: Membangun sebuah linear_congruential_engine obyek. Dengan k = ⌈Log2(m) ÷ 32⌉ dan Sebuah panjang susunan 32 (atau setara) k + 3, memanggil q.generate(a + 0, a + k + 3) dan kemudian menghitung S = (∑j= 0k−1  Sebuahj+3 · 232j) mod m. Jika c mod m adalah 0 dan S adalah 0, menyetel status mesin menjadi 1, yang lainnya menetapkan status mesin ke S.

Mengapa Sebuah0, Sebuah1 dan Sebuah2 dibuang?


6
2018-06-20 16:12


asal


Jawaban:


Ini adalah sesuatu yang saya coba cari tahu sendiri. Saya punya hipotesis, tetapi tidak ada bukti nyata untuk itu. Namun, dokumen yang berasal dari aturan (N2079 sebagaimana yang ditautkan oleh @ T.C.) mengkonfirmasi sebagian dari teori saya.

Perhatikan bahwa fungsi dari aturan yang mengambil dalam std::seed_seq objek dalam dokumen, dan bukan kelas templated. Ini berarti bahwa ketika aturan itu ditulis, itu dibuat khusus untuk std::seed_seq, dan bukan konsep SeedSequence secara umum. Ini berarti kita bisa melihat std::seed_seq kelas untuk informasi tentang ini, khususnya dengan bagaimana std::seed_seq::generate didefinisikan.

Metode itu std::seed_seq::generate penggunaan dijelaskan dengan baik di cppreference.com. Ini agak rumit, tetapi dapat diringkas dalam 4 tahap.

  1. Inisialisasi rentang keluaran dengan beberapa data awal (saya termasuk k=0 sini)

  2. Pindahkan data benih asli ke dalam rentang output (k=1..s)

  3. Perluas data benih ke dalam sisa rentang output (k=s+1..m-1 dimana m=max(s+1, n))

  4. Kocok data dalam rentang output (k=m..m+n-1)

Saat menyemai a std::linear_congruential_engine dengan modulo <= 232 (yang mana termasuk std::minstd_rand dan std::minstd_rand0), seharusnya hanya perlu menghasilkan 1 nilai dari std::seed_seq, tetapi dengan aturan ini, menghasilkan 4. Jadi apa perubahan dalam algoritma ini ketika berubah n dari 1 hingga 4?

Salah satu bagian yang berubah adalah bahwa tahap bergantian berjalan dari 1 iterasi ke 4. Karena salah satu tujuan std::seed_seq adalah untuk menghasilkan nilai-nilai pembibitan yang berkualitas tinggi "diberi benih kecil atau urutan benih awal terdistribusi yang tidak baik.", iterasi pengocok tambahan ini kemungkinan meningkatkan nilai benih yang dihasilkan. Alasan mengapa tetes nilai-nilai 3 pertama bukan yang terakhir adalah karena nanti nilai-nilai (biasanya) yang lebih banyak dikocok.

Ini juga perlu dicatat bahwa persamaan kunci dari semua 4 tahap adalah nilainya begin[k]^begin[k+p]^begin[k−1] (dengan XOR diganti dengan penambahan pada tahap terakhir). Kapan n=1, ini hanya menjadi begin[k] (atau 3*begin[k] untuk tahap terakhir) (perhatikan bahwa "pengindeksan rentang output begin[x] diambil modulo n "dan x % 1 == 0). Kapan n=4Persamaan ini bekerja lebih seperti yang dimaksudkan, yang membantu mengacak data di sekitar dengan lebih efektif.

Jadi jawaban singkatnya adalah itu std::linear_congruential_engine membuang 3 angka yang dihasilkan oleh urutan benih karena memiliki std::seed_seq menghasilkan angka-angka tersebut meningkatkan kualitas nilai-nilai yang sebenarnya digunakan. Sekarang, keputusan untuk membuang angka-angka ini di generator diputuskan sebelum konsep umum SeedSequence didefinisikan, sehingga lebih masuk akal untuk memecahkan masalah di generator, bukannya overcomplicating kelas urutan benih. Namun, ini sekarang berarti bahwa 3 nilai pertama dihasilkan oleh apa saja urutan benih dibuang. Apakah itu layak atau tidak, itu mungkin bisa diperdebatkan, tetapi begitulah sekarang.


1
2017-08-18 06:25