JavaScript nomor acak generator

150

Fungsi JavaScript Math.random()mengembalikan nilai acak antara 0 dan 1, secara otomatis diunggulkan berdasarkan waktu saat ini (mirip dengan Java, saya percaya). Namun, saya tidak berpikir ada cara untuk mengatur benih Anda sendiri untuk itu.

Bagaimana saya bisa membuat generator angka acak yang dapat saya berikan nilai benih saya sendiri, sehingga saya bisa membuatnya menghasilkan urutan nomor acak (pseudo) berulang?

scunliffe
sumber
1
Catatan: Demi menjaga agar pertanyaan ini singkat dan fokus, saya telah membagi kode yang ada di pertanyaan di atas ke jawaban Wiki Komunitas di bawah ini.
Ilmari Karonen
1
Lihat juga stackoverflow.com/questions/521295
Palimondo

Jawaban:

124

Salah satu pilihan adalah http://davidbau.com/seedrandom yang merupakan pengganti drop-in Math.random () yang dapat disemai dengan RC4 dengan properti yang bagus.

David Bau
sumber
18
Sejak saat itu, seedrandom milik David Bau menjadi cukup populer sehingga dipertahankan di sini di github . Sangat disayangkan ECMAScript telah begitu lama kembali sehingga hal-hal seperti ini tidak termasuk dalam bahasa. Serius, tidak ada penyemaian !!!
Makan di Joes
2
@ CatatanJoes, Ini adalah rasa malu dan kemuliaan JS bahwa ini diperlukan dan mungkin. Sangat keren bahwa Anda dapat memasukkan satu file dan mendapatkan perubahan yang kompatibel ke belakang yang dibuat untuk objek Math. Lumayan untuk 10 hari kerja, Brendan Eich.
Bruno Bronosky
2
Bagi siapa pun yang mencari halaman npm untuk proyek ini: npmjs.com/package/seedrandom
Kip
27

Jika Anda tidak memerlukan kemampuan penyemaian, gunakan saja Math.random()dan bangun fungsi pembantu di sekitarnya (mis. randRange(start, end)).

Saya tidak yakin apa RNG yang Anda gunakan, tetapi yang terbaik adalah mengetahui dan mendokumentasikannya sehingga Anda mengetahui karakteristik dan keterbatasannya.

Seperti kata Starkii, Mersenne Twister adalah PRNG yang baik, tetapi tidak mudah untuk diterapkan. Jika Anda ingin melakukannya sendiri, cobalah menerapkan LCG - sangat mudah, memiliki kualitas keacakan yang layak (tidak sebagus Mersenne Twister), dan Anda dapat menggunakan beberapa konstanta populer.

EDIT: pertimbangkan opsi hebat pada jawaban ini untuk implementasi RNG yang dapat diunggulkan pendek, termasuk opsi LCG.

function RNG(seed) {
  // LCG using GCC's constants
  this.m = 0x80000000; // 2**31;
  this.a = 1103515245;
  this.c = 12345;

  this.state = seed ? seed : Math.floor(Math.random() * (this.m - 1));
}
RNG.prototype.nextInt = function() {
  this.state = (this.a * this.state + this.c) % this.m;
  return this.state;
}
RNG.prototype.nextFloat = function() {
  // returns in range [0,1]
  return this.nextInt() / (this.m - 1);
}
RNG.prototype.nextRange = function(start, end) {
  // returns in range [start, end): including start, excluding end
  // can't modulu nextInt because of weak randomness in lower bits
  var rangeSize = end - start;
  var randomUnder1 = this.nextInt() / this.m;
  return start + Math.floor(randomUnder1 * rangeSize);
}
RNG.prototype.choice = function(array) {
  return array[this.nextRange(0, array.length)];
}

var rng = new RNG(20);
for (var i = 0; i < 10; i++)
  console.log(rng.nextRange(10, 50));

var digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
for (var i = 0; i < 10; i++)
  console.log(rng.choice(digits));

orip
sumber
2
Bukankah seharusnya modulus 2 ^ 31? Saya membaca algoritma ini dari wiki .
Trantor Liu
3
Hanya agar Anda sadar, ini bukan "benar" dalam arti tidak menghasilkan apa yang ditentukan oleh matematika. Dengan kata lain, bahasa yang dapat menangani angka besar itu akan memiliki hasil yang berbeda. JS tersedak bilangan besar dan presisi daging (mereka mengapung, setelah semua).
DDS
4
-1 Implementasi LCG ini menghilangkan batas untuk bilangan bulat yang tepat dalam JavaScript karena this.a * this.statekemungkinan menghasilkan angka lebih besar dari 2 ^ 53. Hasilnya adalah rentang keluaran terbatas, dan untuk beberapa benih mungkin periode yang sangat singkat. Lebih lanjut secara umum menggunakan kekuatan dua untuk mmenghasilkan beberapa pola yang cukup jelas, ketika Anda mengeluarkan operasi modulus daripada pemotongan sederhana pula, tidak ada alasan untuk tidak menggunakan prime.
aaaaaaaaaaaa
22

Jika Anda ingin dapat menentukan seed, Anda hanya perlu mengganti panggilan ke getSeconds()dan getMinutes(). Anda bisa memasukkan int dan menggunakan setengahnya mod 60 untuk nilai detik dan setengah modulo 60 lainnya untuk memberi Anda bagian lainnya.

Yang sedang berkata, metode ini terlihat seperti sampah. Melakukan pembangkitan angka acak yang tepat sangat sulit. Masalah yang jelas dengan ini adalah bahwa seed number acak didasarkan pada detik dan menit. Untuk menebak seed dan membuat ulang aliran angka acak Anda hanya perlu mencoba 3600 kombinasi detik dan menit yang berbeda. Ini juga berarti bahwa hanya ada 3600 kemungkinan benih yang berbeda. Ini bisa diperbaiki, tapi saya akan curiga dengan RNG ini sejak awal.

Jika Anda ingin menggunakan RNG yang lebih baik, coba Twister Mersenne . Ini adalah RNG yang teruji dengan baik dan cukup kuat dengan orbit yang sangat besar dan kinerja yang sangat baik.

EDIT: Saya benar-benar harus benar dan merujuk ini sebagai Pseudo Random Number Generator atau PRNG.

"Siapa pun yang menggunakan metode aritmatika untuk menghasilkan angka acak berada dalam keadaan berdosa."
                                                                                                                                                          --- John von Neumann

Starkii
sumber
1
Sebuah link ke JS implementasi dari Mersenne Twister: math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/...
orip
1
@orip Apakah Anda memiliki sumber untuk 3600 kondisi awal? Mersenne Twister diunggulkan dengan angka 32 bit, sehingga PRNG harus memiliki 4 miliar kondisi awal - hanya jika benih awal benar-benar acak.
Tobias P.
2
@TobiasP. Saya merujuk pada saran untuk seed dengan kombinasi getSeconds () dan getMinutes (), 60 * 60 == 3600 kemungkinan kondisi awal. Saya tidak mengacu pada Mersenne Twister.
orip
3
@orip Ok, tidak jelas. Anda mengambil tentang Mersenne Twister dan dalam kalimat berikutnya tentang negara bagian;)
Tobias P.
2
Penanya pertanyaan tidak menyebutkan bahwa mereka memerlukan pembuatan nomor acak "yang tepat" untuk segala jenis aplikasi yang sensitif secara kriptografis. Meskipun semua jawabannya benar, hanya paragraf pertama yang benar-benar relevan dengan pertanyaan yang diajukan. Mungkin menambahkan cuplikan kode dari solusi yang disarankan.
V. Rubinetti
12

Saya menggunakan port JavaScript dari Mersenne Twister: https://gist.github.com/300494 Ini memungkinkan Anda untuk mengatur seed secara manual. Juga, sebagaimana disebutkan dalam jawaban lain, Mersenne Twister adalah PRNG yang sangat bagus.

Christoph Henkelmann
sumber
8

Kode yang Anda daftarkan terlihat seperti Lehmer RNG . Jika demikian, 2147483647bilangan bulat bertanda 32-bit terbesar, 2147483647adalah bilangan prima 32-bit terbesar, dan 48271merupakan pengali periode penuh yang digunakan untuk menghasilkan angka.

Jika ini benar, Anda bisa memodifikasi RandomNumberGeneratoruntuk mengambil parameter tambahan seed, dan kemudian mengatur this.seedke seed; tetapi Anda harus berhati-hati untuk memastikan benih akan menghasilkan distribusi angka acak yang baik (Lehmer bisa aneh seperti itu) - tetapi sebagian besar benih akan baik-baik saja.

mipadi
sumber
7

Berikut ini adalah PRNG yang dapat diberi umpan benih khusus. Memanggil SeedRandomakan mengembalikan fungsi generator acak. SeedRandomdapat dipanggil tanpa argumen untuk menabur kembali fungsi acak yang dikembalikan dengan waktu saat ini, atau dapat disebut dengan 1 atau 2 non-negatif inters sebagai argumen untuk menaburnya dengan bilangan bulat tersebut. Karena akurasi titik float penyemaian dengan hanya 1 nilai hanya akan memungkinkan generator untuk diinisiasi ke salah satu dari 2 ^ 53 negara yang berbeda.

Fungsi generator acak yang dikembalikan mengambil 1 argumen integer bernama limit, batasnya harus dalam kisaran 1 hingga 4294965886, fungsi akan mengembalikan angka dalam kisaran 0 hingga batas-1.

function SeedRandom(state1,state2){
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    if(typeof state1!="number"){
        state1=+new Date()
    }
    if(typeof state2!="number"){
        state2=state1
    }
    state1=state1%(mod1-1)+1
    state2=state2%(mod2-1)+1
    function random(limit){
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        if(state1<limit && state2<limit && state1<mod1%limit && state2<mod2%limit){
            return random(limit)
        }
        return (state1+state2)%limit
    }
    return random
}

Contoh penggunaan:

var generator1=SeedRandom() //Seed with current time
var randomVariable=generator1(7) //Generate one of the numbers [0,1,2,3,4,5,6]
var generator2=SeedRandom(42) //Seed with a specific seed
var fixedVariable=generator2(7) //First value of this generator will always be
                                //1 because of the specific seed.

Generator ini menunjukkan sifat-sifat berikut:

  • Ini memiliki sekitar 2 ^ 64 keadaan batin yang berbeda.
  • Ini memiliki periode sekitar 2 ^ 63, jauh lebih banyak daripada yang dibutuhkan orang secara realistis dalam program JavaScript.
  • Karena modnilai menjadi bilangan prima tidak ada pola sederhana dalam output, tidak peduli batas yang dipilih. Ini tidak seperti beberapa PRNG sederhana yang menunjukkan beberapa pola yang cukup sistematis.
  • Ini membuang beberapa hasil untuk mendapatkan distribusi sempurna terlepas dari batasnya.
  • Ini relatif lambat, berjalan sekitar 10.000 kali per detik pada mesin saya.
aaaaaaaaaaaa
sumber
2
Mengapa ini menghasilkan suatu pola? for (var i = 0; i < 400; i++) { console.log("input: (" + i * 245 + ", " + i * 553 + ") | output: " + SeedRandom(i * 245, i * 553)(20)); }
Timothy Kanski
@TimothyKanski Karena Anda salah menggunakannya. Saya bukan ahli tetapi ini terjadi karena Anda menginisialisasi generator pada setiap iterasi, hanya melihat nilai pertama berdasarkan pada seed, dan BUKAN iterasi pada nomor generator berikutnya. Saya percaya ini akan terjadi pada PRNG mana pun yang tidak memotong benih melintasi interval yang ditentukan.
bryc
5

Jika Anda memprogram dalam Typcript, saya mengadaptasi implementasi Mersenne Twister yang membawa jawaban Christoph Henkelmann ke utas ini sebagai kelas naskah:

/**
 * copied almost directly from Mersenne Twister implementation found in https://gist.github.com/banksean/300494
 * all rights reserved to him.
 */
export class Random {
    static N = 624;
    static M = 397;
    static MATRIX_A = 0x9908b0df;
    /* constant vector a */
    static UPPER_MASK = 0x80000000;
    /* most significant w-r bits */
    static LOWER_MASK = 0x7fffffff;
    /* least significant r bits */

    mt = new Array(Random.N);
    /* the array for the state vector */
    mti = Random.N + 1;
    /* mti==N+1 means mt[N] is not initialized */

    constructor(seed:number = null) {
        if (seed == null) {
            seed = new Date().getTime();
        }

        this.init_genrand(seed);
    }

    private init_genrand(s:number) {
        this.mt[0] = s >>> 0;
        for (this.mti = 1; this.mti < Random.N; this.mti++) {
            var s = this.mt[this.mti - 1] ^ (this.mt[this.mti - 1] >>> 30);
            this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
                + this.mti;
            /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
            /* In the previous versions, MSBs of the seed affect   */
            /* only MSBs of the array mt[].                        */
            /* 2002/01/09 modified by Makoto Matsumoto             */
            this.mt[this.mti] >>>= 0;
            /* for >32 bit machines */
        }
    }

    /**
     * generates a random number on [0,0xffffffff]-interval
     * @private
     */
    private _nextInt32():number {
        var y:number;
        var mag01 = new Array(0x0, Random.MATRIX_A);
        /* mag01[x] = x * MATRIX_A  for x=0,1 */

        if (this.mti >= Random.N) { /* generate N words at one time */
            var kk:number;

            if (this.mti == Random.N + 1)   /* if init_genrand() has not been called, */
                this.init_genrand(5489);
            /* a default initial seed is used */

            for (kk = 0; kk < Random.N - Random.M; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + Random.M] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            for (; kk < Random.N - 1; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + (Random.M - Random.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            y = (this.mt[Random.N - 1] & Random.UPPER_MASK) | (this.mt[0] & Random.LOWER_MASK);
            this.mt[Random.N - 1] = this.mt[Random.M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];

            this.mti = 0;
        }

        y = this.mt[this.mti++];

        /* Tempering */
        y ^= (y >>> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >>> 18);

        return y >>> 0;
    }

    /**
     * generates an int32 pseudo random number
     * @param range: an optional [from, to] range, if not specified the result will be in range [0,0xffffffff]
     * @return {number}
     */
    nextInt32(range:[number, number] = null):number {
        var result = this._nextInt32();
        if (range == null) {
            return result;
        }

        return (result % (range[1] - range[0])) + range[0];
    }

    /**
     * generates a random number on [0,0x7fffffff]-interval
     */
    nextInt31():number {
        return (this._nextInt32() >>> 1);
    }

    /**
     * generates a random number on [0,1]-real-interval
     */
    nextNumber():number {
        return this._nextInt32() * (1.0 / 4294967295.0);
    }

    /**
     * generates a random number on [0,1) with 53-bit resolution
     */
    nextNumber53():number {
        var a = this._nextInt32() >>> 5, b = this._nextInt32() >>> 6;
        return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
    }
}

Anda dapat menggunakannya sebagai berikut:

var random = new Random(132);
random.nextInt32(); //return a pseudo random int32 number
random.nextInt32([10,20]); //return a pseudo random int in range [10,20]
random.nextNumber(); //return a a pseudo random number in range [0,1]

periksa sumber untuk lebih banyak metode.

bennyl
sumber
0

Catatan: Kode ini awalnya termasuk dalam pertanyaan di atas. Demi menjaga agar pertanyaan tetap singkat dan fokus, saya telah memindahkannya ke jawaban Wiki Komunitas ini.

Saya menemukan kode ini menendang sekitar dan tampaknya berfungsi dengan baik untuk mendapatkan nomor acak dan kemudian menggunakan seed sesudahnya tetapi saya tidak yakin bagaimana logika bekerja (misalnya dari mana nomor 2345678901, 48271 & 2147483647 berasal).

function nextRandomNumber(){
  var hi = this.seed / this.Q;
  var lo = this.seed % this.Q;
  var test = this.A * lo - this.R * hi;
  if(test > 0){
    this.seed = test;
  } else {
    this.seed = test + this.M;
  }
  return (this.seed * this.oneOverM);
}

function RandomNumberGenerator(){
  var d = new Date();
  this.seed = 2345678901 + (d.getSeconds() * 0xFFFFFF) + (d.getMinutes() * 0xFFFF);
  this.A = 48271;
  this.M = 2147483647;
  this.Q = this.M / this.A;
  this.R = this.M % this.A;
  this.oneOverM = 1.0 / this.M;
  this.next = nextRandomNumber;
  return this;
}

function createRandomNumber(Min, Max){
  var rand = new RandomNumberGenerator();
  return Math.round((Max-Min) * rand.next() + Min);
}

//Thus I can now do:
var letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
var numbers = ['1','2','3','4','5','6','7','8','9','10'];
var colors = ['red','orange','yellow','green','blue','indigo','violet'];
var first = letters[createRandomNumber(0, letters.length)];
var second = numbers[createRandomNumber(0, numbers.length)];
var third = colors[createRandomNumber(0, colors.length)];

alert("Today's show was brought to you by the letter: " + first + ", the number " + second + ", and the color " + third + "!");

/*
  If I could pass my own seed into the createRandomNumber(min, max, seed);
  function then I could reproduce a random output later if desired.
*/
Ilmari Karonen
sumber
3
Wow, RandomNumberGeneratordan nextRandomNumberfungsinya sebenarnya sudah ada sejak tahun 1996. Seharusnya itu adalah Lehmer / LCG RNG. Ini menggunakan beberapa matematika pintar untuk melakukan modulo aritmatika pada bilangan bulat 32 bit yang seharusnya terlalu kecil untuk mengandung beberapa nilai menengah. Masalahnya, JavaScript tidak mengimplementasikan bilangan bulat 32 bit, melainkan mengapung 64 bit, dan karena pembagiannya bukan pembagian bilangan bulat seperti kode ini menganggap hasilnya bukan generator Lehmer. Memang menghasilkan beberapa hasil yang tampak acak, tetapi jaminan generator Lehmer tidak berlaku.
aaaaaaaaaaaa
1
The createRandomNumberfungsi tambahan kemudian, itu tidak cukup banyak segala sesuatu yang salah, terutama itu instantiates RNG baru setiap kali hal itu disebut, yang berarti bahwa panggilan dalam suksesi cepat semua akan menggunakan pelampung yang sama. Dalam kode yang diberikan hampir tidak mungkin untuk 'a'dipasangkan dengan apa pun kecuali '1'dan'red' .
aaaaaaaaaaaa
-2

OK, inilah solusi yang saya pilih.

Pertama, Anda membuat nilai seed menggunakan fungsi "newseed ()". Lalu Anda meneruskan nilai seed ke fungsi "srandom ()". Terakhir, fungsi "srandom ()" mengembalikan nilai acak semu antara 0 dan 1.

Bit penting adalah bahwa nilai seed disimpan di dalam array. Jika itu hanya bilangan bulat atau float, nilai akan ditimpa setiap kali fungsi dipanggil, karena nilai integer, float, string dan sebagainya disimpan langsung di stack dibandingkan hanya pointer seperti dalam kasus array dan benda lainnya. Dengan demikian, mungkin nilai benih tetap persisten.

Akhirnya, dimungkinkan untuk mendefinisikan fungsi "srandom ()" sehingga merupakan metode dari objek "Math", tetapi saya akan menyerahkannya kepada Anda untuk mencari tahu. ;)

Semoga berhasil!

JavaScript:

// Global variables used for the seeded random functions, below.
var seedobja = 1103515245
var seedobjc = 12345
var seedobjm = 4294967295 //0x100000000

// Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
{
    return [seednum]
}

// Works like Math.random(), except you provide your own seed as the first argument.
function srandom(seedobj)
{
    seedobj[0] = (seedobj[0] * seedobja + seedobjc) % seedobjm
    return seedobj[0] / (seedobjm - 1)
}

// Store some test values in variables.
var my_seed_value = newseed(230951)
var my_random_value_1 = srandom(my_seed_value)
var my_random_value_2 = srandom(my_seed_value)
var my_random_value_3 = srandom(my_seed_value)

// Print the values to console. Replace "WScript.Echo()" with "alert()" if inside a Web browser.
WScript.Echo(my_random_value_1)
WScript.Echo(my_random_value_2)
WScript.Echo(my_random_value_3)

Lua 4 (lingkungan target pribadi saya):

-- Global variables used for the seeded random functions, below.
seedobja = 1103515.245
seedobjc = 12345
seedobjm = 4294967.295 --0x100000000

-- Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
    return {seednum}
end

-- Works like random(), except you provide your own seed as the first argument.
function srandom(seedobj)
    seedobj[1] = mod(seedobj[1] * seedobja + seedobjc, seedobjm)
    return seedobj[1] / (seedobjm - 1)
end

-- Store some test values in variables.
my_seed_value = newseed(230951)
my_random_value_1 = srandom(my_seed_value)
my_random_value_2 = srandom(my_seed_value)
my_random_value_3 = srandom(my_seed_value)

-- Print the values to console.
print(my_random_value_1)
print(my_random_value_2)
print(my_random_value_3)
posfan12
sumber
PS - Saya belum terbiasa dengan Stack Overflow, tapi mengapa posting tidak dalam urutan kronologis?
posfan12
Hai @ posfan12 - jawaban atas pertanyaan biasanya didaftar berdasarkan "upvotes" sehingga "cream naik ke atas". Namun untuk memastikan tampilan jawaban yang adil dengan skor yang sama, mereka ditampilkan secara acak. Karena ini awalnya pertanyaan saya ;-) Saya pasti akan segera memeriksanya. Jika saya (atau orang lain) menganggap jawaban ini bermanfaat, kami akan membatalkannya, dan jika saya menganggapnya sebagai jawaban "benar", Anda akan melihat tanda centang hijau ditambahkan ke jawaban ini juga. - Selamat datang di StackOverflow!
scunliffe
2
-1 Implementasi LCG ini menghilangkan batas untuk bilangan bulat yang tepat dalam JavaScript karena seedobj[0] * seedobjakemungkinan menghasilkan angka lebih besar dari 2 ^ 53. Hasilnya adalah rentang keluaran terbatas, dan untuk beberapa benih mungkin periode yang sangat singkat.
aaaaaaaaaaaa