Google Chrome 49で正しい乱数が返ってくるようになった模様

dorako321

8年前

Math.random()関数は0~1の間の少数を含む値をランダムに返します。V8含むJavascriptエンジンでは擬似乱数数ジェネレータ(PRNG)を使ってMath.random()を実装しています。

擬似乱数とは、乱数のように見えて、実際には計算によって求めている、規則性や再現性がある乱数のことです。擬似乱数が本物の乱数と(統計的に見て)見分けが付かない状態だと質の良い擬似乱数であると言えます。

最近までV8エンジンは擬似乱数ジェネレータとしてMWC1616(multiply with carry, combining two 16-bit parts)と言われるアルゴリズムを使用していました。githubにあるコードは以下のようです。

function MathRandom() {
  var r0 = (MathImul(18030, rngstate_0) + rngstate_1) | 0;
  var r1 = (MathImul(36969, rngstate_2) + rngstate_3) | 0;
  rngstate_0 = r0 & 0xFFFF;
  rngstate_1 = r0 >>> 16;
  rngstate_2 = r1 & 0xFFFF;
  rngstate_3 = r1 >>> 16;
  // Construct a double number 1.<32-bits of randomness> and subtract 1.
  return %_ConstructDouble(0x3FF00000 | (r0 & 0x000FFFFF), r1 & 0xFFF00000) - 1;
}

function MathRandom() {

var r0 = (MathImul(18030, rngstate_0) + rngstate_1) | 0;

var r1 = (MathImul(36969, rngstate_2) + rngstate_3) | 0;

rngstate_0 = r0 & 0xFFFF;

rngstate_1 = r0 >>> 16;

rngstate_2 = r1 & 0xFFFF;

rngstate_3 = r1 >>> 16;

// Construct a double number 1.<32-bits of randomness> and subtract 1.

return %_ConstructDouble(0x3FF00000 | (r0 & 0x000FFFFF), r1 & 0xFFF00000) - 1;

}

このアルゴリズムに問題があり、実際に出力するとBeforeの画像のような規則が見える、乱数っぽくない出力となっていたようです。

V8エンジンが修正され、現在はXorShift128関数によるランダムが採用されたようです。

  static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
    uint64_t s1 = *state0;
    uint64_t s0 = *state1;
    *state0 = s0;
    s1 ^= s1 << 23;
    s1 ^= s1 >> 17;
    s1 ^= s0;
    s1 ^= s0 >> 26;
    *state1 = s1;
  }

static inline void XorShift128(uint64_t* state0, uint64_t* state1) {

uint64_t s1 = *state0;

uint64_t s0 = *state1;

*state0 = s0;

s1 ^= s1 << 23;

s1 ^= s1 >> 17;

s1 ^= s0;

s1 ^= s0 >> 26;

*state1 = s1;

}

そしてこの修正はChrome 49で反映されたようです。

Google Chrome’s JavaScript engine finally returns actual random numbers

他のJavascriptエンジンとの乱数比較するとおもしろそうですね。