JavaScript nomor acak generator

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?

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

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));

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

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.

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.

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.

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.

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.
*/

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)