Apakah 161803398 Nomor A 'Spesial'? Di dalam Math.Random ()

162

Saya menduga jawabannya adalah ' Karena Matematika ', tetapi saya berharap seseorang dapat memberikan sedikit lebih banyak wawasan di tingkat dasar ...

Saya mencari-cari kode sumber BCL hari ini, melihat bagaimana beberapa kelas yang saya gunakan sebelumnya benar-benar diimplementasikan. Saya tidak pernah berpikir tentang cara membuat angka acak (semu) sebelumnya, jadi saya memutuskan untuk melihat bagaimana hal itu dilakukan.

Sumber lengkap di sini: http://referencesource.microsoft.com/#mscorlib/system/random.cs#29

private const int MSEED = 161803398;

Nilai MSEED ini digunakan setiap kali kelas Random () diunggulkan.

Bagaimanapun, saya melihat 'angka ajaib' ini - 161803398 - dan saya tidak memiliki ide foggiest mengapa nomor itu dipilih. Ini bukan bilangan prima atau kekuatan 2. Ini bukan 'setengah jalan' ke nomor yang tampak lebih signifikan. Saya melihatnya dalam biner dan hex dan well, itu hanya tampak seperti angka bagi saya.

Saya mencoba mencari nomor di Google, tetapi saya tidak menemukan apa pun.

c# .net algorithm random Rob P.
sumber

kemungkinan duplikat dari dua benih berbeda yang menghasilkan urutan 'acak' yang sama

MethodMan

@ 48klocs: Dikatakan demikian dalam dokumen :

The current implementation of the Random class is based on Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.

Jesse Good

@ 48klok Ya, halaman 283 di sini: apps.nrbook.com/c/index.html Alasannya tampaknya "karena matematika".

eshs

@ shs: Fakta menarik: Halaman 283 dari tautan Anda menunjukkan inextp = 31;, tetapi kode sumber Randomkelas memilikinya inextp = 21;karena ada yang salah ketik yang menyebabkan bug ini .

Jesse Good

@Izkata Kita perlu mendidik pengguna tentang perilaku yang benar (tidak memilih untuk menutup secara keliru) untuk tujuan jangka panjang kualitas situs, bukan hanya bertujuan untuk tujuan jangka pendek (tidak memiliki pertanyaan khusus yang ditutup). Dan jika saya tidak menunjukkan komentar di atas, itu mungkin sudah ditutup sebagai duplikat karena orang kadang-kadang melakukannya.

Bernhard Barker

Jawaban:

141

Tidak, tapi ini didasarkan pada Phi ("rasio emas").

161803398 = 1.61803398 * 10^8 ≈ φ * 10^8

Lebih lanjut tentang rasio emas di sini .

Dan bacaan yang sangat bagus untuk ahli matematika kasual di sini .

Dan saya menemukan makalah penelitian tentang generator angka acak yang setuju dengan pernyataan ini. (Lihat halaman 53.)

Matt Johnson-Pint
sumber

Tahukah Anda mengapa angka berdasarkan Phi membuat pilihan yang baik sebagai benih? Apakah mungkin untuk meringkas ini di sini?

Bernhard Barker

@Dukeling Konstanta digunakan tepat sekali, untuk meredam benih yang masuk. Kecurigaan saya yang sangat kuat adalah bahwa itu dipilih untuk menjadi apa - apa atas nomor lengan saya yang mencegah benih dengan beberapa bit yang ditetapkan (mungkin pilihan umum) dari mengacaukan generator nomor acak (bukan beberapa properti magis phi).

David Eisenstat

Mengutip kutipan dari buku tersebut Menurut Knuth setiap MBIG besar dan yang lebih kecil (tapi masih besar) MSEED dapat diganti dengan nilai-nilai di atas. Jadi itu menyenangkan secara matematis, lebih atau kurang .. Jadi jawaban yang benar seharusnya: Tidak. Tapi ini didasarkan pada Phi.

TaW

Hanya melihat-lihat kertas nomor acak - garis ini sedikit menonjol -

"One  can’t even fathom the repercussions if security flaws in the implementation (or design) of the SSL  protocol are to be found."

(halaman 4)

jcw

Saya akan berpikir bahwa cara yang lebih relevan untuk menggunakan rasio emas adalah menggunakan (modulus / phi) daripada menggunakan representasi basis-10 dari digit dalam kode yang tidak ada hubungannya dengan basis 10. Karakteristik phi yang menarik Saya tidak melihat pada halaman itu bahwa dari apa yang saya tahu, untuk setiap bilangan bulat N, nilai N / phi-int (N / phi)> = 1 / N / sqrt (5). Itu berarti bahwa bahkan jika seseorang menghasilkan urutan angka N / phi-int (N / phi), jarak antara pasangan terdekat akan berada dalam faktor sqrt (5) dari jarak seragam yang mungkin terbesar dalam interval ( 0..1)

supercat

Angka ini diambil dari rasio emas 1.61803398 * 10 ^ 8 . Matt memberikan jawaban yang bagus tentang apa nomor ini, oleh karena itu saya hanya akan menjelaskan sedikit tentang suatu algoritma.

Ini bukan nomor khusus untuk algoritma ini. Algoritma ini adalah algoritma penghasil angka acak subtraktif Knuth dan poin utamanya adalah:

menyimpan daftar melingkar dari 56 angka acak
inisialisasi adalah proses mengisi daftar, kemudian mengacak nilai-nilai tersebut dengan algoritma deterministik tertentu
dua indeks disimpan yaitu 31 terpisah
angka acak baru adalah perbedaan dari dua nilai di dua indeks
simpan nomor acak baru dalam daftar

Generator didasarkan pada rekursi berikut: X _n = (X _n-55 - X _n-24 ) mod m, di mana n ≥ 0. Ini adalah kasus parsial generator Fibonacci yang tertunda : X _n = (X _n-j @ X _n-k ) mod m, di mana 0 <k <j dan @ adalah operasi biner (pengurangan, penjumlahan, xor).

Ada beberapa implementasi generator ini. Knuth menawarkan implementasi dalam FORTRAN dalam bukunya. Saya menemukan kode berikut , dengan komentar berikut:

PARAMETER (MBIG = 1000000000, MSEED = 161803398, MZ = 0, FAC = 1.E-9)

Menurut Knuth, setiap MBIG besar, dan MSEED yang lebih kecil (tapi masih besar) dapat diganti dengan nilai-nilai di atas.

Sedikit lebih banyak dapat ditemukan di sini Catatan, bahwa ini sebenarnya bukan makalah penelitian (seperti yang dinyatakan oleh Math), ini hanya tesis master.

Orang-orang di kriptografi seperti menggunakan nomor irasional ( pi, e, sqrt(5)) karena ada dugaan bahwa angka dari nomor tersebut muncul dengan frekuensi yang sama dan dengan demikian memiliki tinggi entropi . Anda dapat menemukan pertanyaan terkait ini di pertukaran stack keamanan untuk mempelajari lebih lanjut tentang nomor tersebut. Berikut ini kutipannya:

"Jika konstanta dipilih secara acak, maka dengan probabilitas tinggi, tidak ada penyerang yang bisa melanggarnya." Tetapi cryptographers, yang merupakan kelompok paranoid, skeptis ketika seseorang berkata, "Mari kita gunakan set konstanta ini. Saya memilihnya secara acak, saya bersumpah ." Jadi sebagai kompromi, mereka akan menggunakan konstanta seperti, katakanlah, ekspansi biner π. Meskipun kami tidak lagi memiliki manfaat matematis karena memilih mereka secara acak dari sejumlah besar angka, kami setidaknya bisa lebih percaya diri bahwa tidak ada sabotase.

Salvador Dali
sumber

Sedangkan untuk penjawab, itu bukan hanya karena entropi mereka, itu juga karena angka-angka itu berlipat ganda karena tidak ada yang melebihi angka lengan saya .

Cole Johnson