Math.random() は内部的に何を行っているのか。

乱数を生成する有名なメソッドと聞くと、JavaScriptの組み込みメソッドのMath.random()が思いつくと思います

これが内部的にどの様な実装になっているのかが気になったので調べて見ました。

Math.random() の実装

どうやら Xorshiftというアルゴリズムを使っている様です。
メモリもあまり使わず高速なんだとか。ただ完全にランダムな訳では無いと。

Xorshiftについて調べると以下のように出ます。
XOR演算のみを使用した疑似乱数生成アルゴリズム

実装のCのソースが乗っていたのでTypeScriptに直してみました。

class Xorshift64State {
  constructor(public a: number) {}
}

function xorshift64(state: Xorshift64State): number {
  let x = state.a;
  x ^= x << 7;
  x ^= x >>> 9;
  state.a = x;
  return x;
}


const init = new Xorshift64State(1);
console.log(xorshift64(init))
console.log(xorshift64(init))

const init2 = new Xorshift64State(2);
console.log(xorshift64(init2))

実行結果

[LOG]: 129 
[LOG]: 16417 
[LOG]: 258 

init、init2のinstanceの 1,2 の部分がシードと呼ばれる部分です。
1, 2の初期値を Date.now() 等にすればある程度の乱数にはなると思います。
またインスタンスの内部で前の数字が入れ替わっているので同じインスタンスで生成可能です。

大枠は分かったので
おそらく気になるのが、この部分だと思います。
前提知識として簡単なbitの知識が必要です。

x ^= x << 7;
x ^= x >>> 9;

排他的論理和

^=はXOR演算子を意味します。
XORとは排他的論理和と言い、 ビットでは二つのビットの内、一つだけ真(1)ならば真(1)を返します。
JavaScriptにおいては

let x = 10;
x ^= 6;
console.log(x)

の場合、^=の部分で、10はビットに直され00001010となります。
6は00000110となります。
00001010 XOR 00000110では、00001100となります。
10進数に直すと、 12 です。

シフト

let x = 10;
x = 1 << x;
console.log(x)

10のビットは00001010です。簡単に言うとこのビットがどちらかに動かされます。
<< では左方向、>> では右方向です。
例のコードでは x(00001010) を左に一つシフトさせています。
つまり 00001010 => 00010100となります。
これによって、x は 00010100を10進数に直すと、1024になります。

>> は、左にずらした時に溢れた分は廃棄します。 もし負数を表しているとしても符号はそのままです。
>>> は符号を表す部分を残しません。

コードを追ってみる

本題の部分にもどります。

x ^= x << 7;
x ^= x >>> 9;

x に数を入れて変化を追ってみます。

let x = 8; // 00001000
x ^= x << 7;
x ^= x >>> 9;
console.log(x);

まず2行目では左シフトが7回分実行されます。
00000001000 => 10000000000
10進数では 1024 になります。
これに XORが適応されます。
00000001000 XOR 10000000000 => 10000001000
10000001000 は 1032に相当します。

三行目では 符号なし右シフトが9回実行されます。
10000001000 => 00000000010
00000000010は 2 に相当します。
これに XORが適応されます。
00000000010 XOR 10000001000 => 10000001010
1034に相当します。

よって結果は 1034となります。
他の数でも試しましたが、シード(x)が1違うだけでも大きく数が動きます。 (被りは自分の生成結果の中では見られませんでした。)

ベンチマークをしてみましたが、 10万回ほどの処理で 1ms 超高速ですね

補足

XORSHIFTの演算のシフト数はこの数のみには限られません。 詳しく話すとこの記事の文字数が5桁になるので控えますが、 数理的な詳しい仕組みを知りたいという方は、こちらの記事が参考になります。

再実装

Math.random() を再実装してみました。

let seed = Date.now();

function Random() {
    seed ^= seed << 7;
    seed ^= seed >>> 9;

    return Math.min(1, Math.abs(seed) / 2000000000);
}

console.log(Random());
console.log(Random());
console.log(Random());

(ただしこれはどう考えてもベストプラクティスでは無いので実際には使わないでください。)

実行結果

[LOG]: 0.7331030055
[LOG]: 0.2236895000
[LOG]: 0.6686849910

いい感じにランダムになってますね。

最後に

疑似乱数生成アルゴリズムには他にも 線形合同法 や 減算乱数生成アルゴリズム等が有ります。 これらも気になりますね。
Math.random()の他にも、WebAPIには 知っている人は結構居ると思いますが、crypto.getRandomValues() という暗号強度の高い乱数を生成する関数が有ります。
仕様はここに書いて有ります。 暗号的に安全性が求められる場合はこっちを使った方が良さそうですね。

他にも記事を書いています！
是非ここからご覧下さい！
https://ame-x.net