Menyemai penjana nombor rawak dalam Javascript

Question

Adakah mungkin untuk menyemai penjana nombor rawak (Math.random) dalam JavaScript?

Answer 1

Tidak, tidak boleh menyemai benih Math.random(). Spesifikasi ECMAScript sengaja samar-samar mengenai subjek, tidak memberikan kaedah pembenihan atau memerlukan penyemak imbas untuk menggunakan algoritma yang sama. Jadi fungsi sedemikian perlu disediakan secara luaran, yang untungnya tidak terlalu sukar.

Saya melaksanakan beberapa fungsi Pseudo-Random Number Generator (PRNG) yang bagus, pendek dan pantas dalam JavaScript tulen. Semua ini boleh disemai dan memberikan nombor berkualiti tinggi. Ini bukan untuk tujuan keselamatan - jika anda memerlukan CSPRNG yang boleh disemai, lihat ISAAC.

Pertama, berhati-hati untuk memulakan PRNG anda dengan betul. Untuk memudahkan, penjana di bawah tidak mempunyai proses penjanaan benih terbina dalam, tetapi menerima satu atau lebih nombor 32-bit sebagai keadaan benih awal PRNG. Biji benih yang serupa atau jarang (cth. benih ringkas 1 dan 2) mempunyai entropi yang rendah dan boleh menyebabkan korelasi atau isu kualiti rawak yang lain, kadangkala menghasilkan output dengan sifat yang serupa (cth. aras yang dijana secara rawak adalah serupa). Untuk mengelakkan ini, amalan terbaik adalah untuk memulakan PRNG dengan benih entropi tinggi yang diedarkan secara seragam dan/atau memajukan melebihi 15 nombor pertama atau lebih.

Terdapat banyak cara untuk melakukan ini, tetapi ini dua. Pertama, fungsi hash sangat bagus untuk menjana benih daripada rentetan pendek. Walaupun dua rentetan adalah serupa, fungsi cincang yang baik akan menghasilkan hasil yang sangat berbeza, jadi anda tidak perlu terlalu memikirkan rentetan itu. Berikut ialah contoh fungsi cincang:

function cyrb128(str) {
    let h1 = 1779033703, h2 = 3144134277,
        h3 = 1013904242, h4 = 2773480762;
    for (let i = 0, k; i < str.length; i++) {
        k = str.charCodeAt(i);
        h1 = h2 ^ Math.imul(h1 ^ k, 597399067);
        h2 = h3 ^ Math.imul(h2 ^ k, 2869860233);
        h3 = h4 ^ Math.imul(h3 ^ k, 951274213);
        h4 = h1 ^ Math.imul(h4 ^ k, 2716044179);
    }
    h1 = Math.imul(h3 ^ (h1 >>> 18), 597399067);
    h2 = Math.imul(h4 ^ (h2 >>> 22), 2869860233);
    h3 = Math.imul(h1 ^ (h3 >>> 17), 951274213);
    h4 = Math.imul(h2 ^ (h4 >>> 19), 2716044179);
    h1 ^= (h2 ^ h3 ^ h4), h2 ^= h1, h3 ^= h1, h4 ^= h1;
    return [h1>>>0, h2>>>0, h3>>>0, h4>>>0];
}

Panggil cyrb128 akan menjana nilai cincang 128-bit daripada rentetan, yang boleh digunakan untuk menyemai PRNG. Begini cara anda boleh menggunakannya:

// Create cyrb128 state:
var seed = cyrb128("apples");
// Four 32-bit component hashes provide the seed for sfc32.
var rand = sfc32(seed[0], seed[1], seed[2], seed[3]);

// Only one 32-bit component hash is needed for mulberry32.
var rand = mulberry32(seed[0]);

// Obtain sequential random numbers like so:
rand();
rand();

Nota: Jika anda mahukan cincangan 128-bit yang berkuasa sedikit, pertimbangkan MurmurHash3_x86_128, yang lebih teliti tetapi direka bentuk untuk berfungsi dengan tatasusunan yang besar.

Sebagai alternatif, cuma pilih beberapa data tiruan untuk mengisi benih dan memajukan penjana beberapa kali (12-20 lelaran) terlebih dahulu untuk mencampurkan keadaan awal secara menyeluruh. Ini mempunyai faedah sebagai lebih mudah dan sering digunakan dalam pelaksanaan rujukan PRNG, tetapi ia mengehadkan bilangan keadaan awal:

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

Nota: Output fungsi PRNG ini menjana nombor 32-bit positif (0 hingga 2³²-1), yang kemudiannya ditukar kepada nombor titik terapung antara 0-1 (0 termasuk, 1 tidak termasuk) bersamaan dengan Math.random() , jika anda mahukan julat nombor rawak tertentu, baca artikel ini di MDN. Jika anda hanya mahu bit asal, keluarkan sahaja operasi pembahagian terakhir.

Nombor JavaScript hanya boleh mewakili integer sehingga resolusi 53-bit. Apabila operasi bitwise digunakan, nilai ini dikurangkan kepada 32. PRNG moden dalam bahasa lain selalunya menggunakan operasi 64-bit, yang memerlukan shim apabila mengalihkan ke JS, yang boleh secara ketara merendahkan prestasi. Algoritma di sini hanya menggunakan operasi 32-bit kerana ia serasi secara langsung dengan JS.

---

sfc32 (kaunter cepat mudah)

sfc32 adalah sebahagian daripada suite ujian nombor rawak PractRand (ia lulus sudah tentu). sfc32 mempunyai keadaan 128-bit dan sangat pantas dalam JS.

function sfc32(a, b, c, d) {
    return function() {
      a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0; 
      var t = (a + b) | 0;
      a = b ^ b >>> 9;
      b = c + (c << 3) | 0;
      c = (c << 21 | c >>> 11);
      d = d + 1 | 0;
      t = t + d | 0;
      c = c + t | 0;
      return (t >>> 0) / 4294967296;
    }
}

Anda mungkin tertanya-tanya | 是什么？ 0 和 >>>= 0 是用于。这些本质上是 32 位整数转换，用于性能优化。 JS 中的 Number Pada asasnya kesemuanya ialah nombor titik terapung, tetapi apabila melakukan operasi bitwise, ia bertukar kepada mod integer 32-bit. Mod ini diproses dengan lebih pantas oleh penterjemah JS, tetapi sebarang pendaraban atau penambahan akan menyebabkannya bertukar kembali ke titik terapung, menyebabkan prestasi hit.

Mulberi 32

Mulberry32 ialah penjana ringkas dengan keadaan 32-bit, tetapi sangat pantas dan mempunyai rawak yang baik (pengarang mengatakan ia melepasi suite ujian gjrand dengan kitaran penuh 2³², tetapi saya belum mengesahkannya lagi) .

function mulberry32(a) {
    return function() {
      var t = a += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

Saya akan mengesyorkan ini jika anda hanya memerlukan PRNG yang ringkas tetapi sopan dan tidak memerlukan berbilion nombor rawak (lihat soalan hari jadi).

xoshiro128**

Sehingga Mei 2018, xoshiro128** ialah ahli baharu keluarga Xorshift , dibangunkan oleh Vigna dan Blackman (Profesor Vigna juga bertanggungjawab untuk algoritma Xorshift128+, yang menguasai kebanyakan Math.random pelaksanaan). Ia adalah penjana terpantas yang menyediakan keadaan 128-bit.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = b * 5; r = (r << 7 | r >>> 25) * 9;
        c ^= a; d ^= b;
        b ^= c; a ^= d; c ^= t;
        d = d << 11 | d >>> 21;
        return (r >>> 0) / 4294967296;
    }
}

Pengarang mendakwa bahawa ia lulus ujian rawak dengan sangat baik (walaupun ada kaveat). Penyelidik lain menyatakan bahawa ia gagal beberapa ujian dalam TestU01 (terutamanya LinearComp dan BinaryRank). Dalam amalan, ia tidak sepatutnya menyebabkan masalah apabila bekerja dengan nombor titik terapung (seperti dalam pelaksanaan ini), tetapi mungkin jika bergantung pada bit tertib terendah asal.

JSF (Jenkins Fast)

Ini adalah JSF atau "smallprng" pertama oleh Bob Jenkins (2007). dan Ghost Hash. Ia lulus ujian PractRand dan sepatutnya pantas, walaupun tidak sepantas sfc32.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

Answer 2

Tidak, tidak mungkin untuk menyemai Math.random(), tetapi agak mudah untuk menulis penjana anda sendiri, atau lebih baik lagi, gunakan yang sedia ada.

Lihat: Soalan berkaitan ini.

Juga, lihat blog David Bau untuk maklumat lanjut tentang menyemai.