JavaScriptで開発していたFEH のガチャシミュレーターの計算処理をWebAssembly(C++)に移植したんですが、そのときにガチャの選出に利用する疑似乱数をどのように取得するかで迷いました。ちなみにJavaScriptのMath.random()の実装はブラウザの実装依存とのことですが、こちらの情報によると、2016年頃のメジャーブラウザではどれも Xorshift128+ というアルゴリズムが採用されていたらしいです(現在も同様かどうかは調べてません)。
ということで、ガチャシミュレーターの疑似乱数生成アルゴリズムを切り替えられるようにして、それぞれのアルゴリズムによる処理速度の違いを比較してみました。実行環境の詳細は割愛しますが、Windows の結構古い Core i7 が積まれたマシンで、msvc で /O2 最適化オプションを指定してコンパイルしたものを使用して計測します。WebAssembly 作る時は clang が使われるので、本当は clang でコンパイルして比較した方が良さそうですが、今回はガチャシミュの実運用環境のことはあまり気にしない事にします。
比較結果
以下が、35回ガチャを引くシミュレートを100万回繰り返した平均時間を計測した結果です。35回というのはFEHで1フェーと呼ばれる1度に課金できる最高額でのガチャ可能回数です。
| アルゴリズム | シミュレート時間(ms) |
|---|---|
| 線形合同法 | 51.42 |
| メルセンヌ・ツイスタ(mt19937) | 41.10 |
| Xorshift128 | 38.72 |
| Xoroshiro128** | 35.62 |
純粋に疑似乱数生成だけを計測した訳ではないので、この差がそのまま乱数生成時間ではない点には注意しないといけないですが、結構差が出る結果となりました。
線形合同法は乱数の質も低いけど、速度は速いのかなとか勝手に思ってたんですが、速度も大分遅いんですね。C言語では一番簡単に使えるという点はメリットですが、速度や質においてはいい事なし。
各アルゴリズムの疑似乱数の質については検証していませんが、Webで調べてみると、mt19937 が疑似乱数の一様さや周期の面で最も質が良いみたいですね。Xoroshiro128** も質はそこそこ良いらしいので、速度面の優位性で、ガチャシミュレーターの疑似乱数には Xoroshiro128** をとりあえず採用しておくのが良さそうかなと思いました。
各アルゴリズムの実装
検証に使ったプログラムの各アルゴリズムの実装について補足しておきます。Cの rand() 関数が線形合同法が使われているとのことだったので、rand()を使用しています。mt19937 は std::mt19937 を使用しました。Xorshift128 と Xoroshift128** については以下のページを参考に実装しました。
Xorshift128の実装参考
https://ja.wikipedia.org/wiki/Xorshift
