Sumber asli `(seed * 9301 + 49297)% 233280` algoritma acak?

9

Jika Anda mencari contoh membuat generator angka acak (semu), Anda akan mengalami hal-hal seperti ini (contoh spesifik http://indiegamr.com/generate-repeatable-random-numbers-in-js/ ):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Angka-angka spesifik (9301, 49297, 233280) dan algoritma digunakan berulang kali, tetapi tampaknya tidak ada yang memiliki referensi pasti untuk ini. Siapa yang menemukan algoritma ini dan menguji distribusi? Apakah ada kertas atau sesuatu untuk dikutip?

jlarson
sumber
5
itu adalah generator kongruen linier tetapi dengan periode yang cukup kecil (hanya 233k sedangkan int 32 bit memungkinkan memiliki periode 4 miliar
ratchet freak
1
Orang sering menyalin kode langsung dari buku, jadi mungkin dari buku lama di suatu tempat dan telah disalin beberapa kali. Ini juga tampaknya menjadi kasus yang membatasi. Mungkin bermanfaat: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/... ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Apa pun asalnya, itu adalah nilai yang mengerikan untuk digunakan untuk menghitung benih.
3
@ jlarson komentar hampir tidak cukup lama, tetapi ada dua masalah yang dihadapi. Pertama, seperti yang disinggung oleh ratchet, modulo adalah periode maksimum : jumlah angka unik sebelum generator berulang. Periode aktual mungkin lebih kecil. Kedua, dua angka lainnya (kebanyakan multiplicand) harus relatif prima ke nomor modulo untuk memastikan periode yang lebih lama. Idealnya bilangan modulo adalah bilangan prima terbesar kurang dari bilangan bulat positif maksimum yang cocok dengan tipe data, dan dua bilangan lainnya juga bilangan prima besar.
1
Itu adalah versi singkat dan singkat mengapa angka-angka itu mengerikan, mengingat ini adalah diskusi sampingan dan menambahkan jawaban yang sebenarnya tidak sesuai untuk pertanyaan ini. Saya sarankan untuk menjelajahi Wikipedia dan mungkin Matematika atau Ilmu Komputer untuk info lebih lanjut, walaupun secara teknis algoritma nomor pseudorandom juga ada di topik di Programmer.

Jawaban:

7

Pencarian cepat Google Buku menunjukkan angka-angka ini (9301, 49297, 233280) telah digunakan dalam sejumlah referensi:

  • Resep Numerik dalam FORTRAN 77
  • Pengantar Metode Numerik dalam C ++
  • Sumber Daya Pengembang CGI: Pemrograman Web dalam TCL dan PERL
  • Fortran 77 yang Efektif untuk Insinyur & Ilmuwan
  • Pengembangan JavaScript
  • Semua di C
  • Java Contoh Singkatnya
  • Algoritma seminarial
  • Pengantar Mekanika

Yang tertua adalah metode Komputer tahun 1977 untuk perhitungan matematis oleh George Elmer Forsythe, Michael A. Malcolm, Cleve B. Moler (Prentice-Hall), meskipun Google tidak menunjukkan di mana teks itu digunakan dalam buku sehingga tidak dapat diverifikasi.

Teks yang paling awal ditampilkan adalah Resep Numerik dalam Pascal (Edisi Pertama): Seni Komputasi Ilmiah , Volume 1 oleh Press, Teukolsky, Vetterling dan Flannery dalam tabel satu halaman penuh "Konstanta untuk Generator Angka Acak Portabel". Angka-angka khusus ini diberikan dengan limpahan pada 2 ^ 31.

The Numerical Recipes serangkaian buku yang sangat populer, dan telah di cetak sejak tahun 1986.

Hugo
sumber
1
Wow, jika jawabannya tidak ada di sini saya tidak tahu di mana itu akan berada. Terima kasih .. // Aku berharap bisa menunjukkan penelitian spesifik mengapa angka-angka ini istimewa, tapi ini sudah cukup. 9301 adalah produk dari dua bilangan prima (71x131), 49297 adalah bilangan prima - secara naluriah saya merasa seperti itu harus relevan. 233280 bukan prime - sama dengan 2x2x2x2x2x2x3x3x3x3x3x3x5 (atau 2 ^ 6 * 3 ^ 5 * 5)
jlarson