PHP の壊れた mt_rand の品質を統計的に検証した
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？
ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します．
壊れた mt_rand とは
PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．このバグのある mt_rand の実装をこの記事では「壊れた mt_rand」と呼びます．
今回話題となっている一連の騒動は，
- kusano さんが壊れている mt_rand を修正する pull request を送り，一度マージされた．
- でも，後方互換性を崩す，とリバートされた．
- それどころか，壊れていることが維持されるようにテストがついた．
といった感じだと思います．
詳しくは以下のブログ記事にまとまってますので是非．
なぜ擬似乱数の品質は重要なのか？
擬似乱数が「ちゃんと乱数に近い」ことは，統計的な実験やシミュレーション，確率的アルゴリズム，暗号，ゲーム等に欠かすことのできない要因です．
例えば最近だと，「グラブル問題」などソシャゲのガチャの確率の話をよく聞きます．意図的にガチャの確率を弄っている場合まだ良い（……良くはないですが少なくとも運営の意図通りではあるしすぐ直せる）として，擬似乱数の性質が要因でバグとして確率の偏りが起こってしまうと，とても悲惨だと思います．
BigCrush テストとは
ここ最近での乱数のテストといったら，BigCrush だと思います．
例えば，Google Chrome で採用され話題になった xorshift128+ の作者公式サイトでも，BigCrush でのテスト結果が（自慢気に）載ってます．
Here quality is measured using the powerful BigCrush suite of tests.
http://xorshift.di.unimi.it/
メルセンヌ・ツイスター作者の松本先生の最近の研究でも，品質で真っ先に言及されるテストが BigCrush です．
XORSHIFT-ADD は128ビットの内部状態空間と2128-1の周期を 持ち、 TestU01 の bigcrush test を通ります。
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/
BigCrush は，統計的なテストを大量に実行します．数学的に解析を行うことのできるシミュレーション等を擬似乱数を用いて実行し，「本当に乱数だったらこういう確率分布になるはず」という分布と実際の結果から検定を行います．
どういうメニューがあるかは，Diehard Test の Wikipedia 記事を見るとイメージが湧きやすいかも．BigCrush は 10 時間近く乱数を生成し続け 160 種類のテストを実行します．（Diehard より BigCrush のほうがテストが豊富）
結果
PHP の mt_rand のコードを取り出してきて，BigCrush に掛けるためのコードを書きました．
上述の xorshift128+ の公式サイトを参考にして，適当な 100 個のシードで BigCrush を実行し，落ちたテストの数を表にしました．
| アルゴリズム | 落ちたテスト（16000 個中） |
|---|---|
| 壊れた mt_rand | 230 |
| 修正済 mt_rand | 236 |
なんと，ほとんど差が無いんですね．むしろ「壊れた」って呼ぶのが失礼かもしれないぐらいです．上述の xorshift128+ 公式に載ってるメルセンヌ・ツイスターの結果とそこそこ合致してると思うので，テストは正しくできているのではないかと思います．あと，C 言語の stdlib の rand も実行してみましたが，こちらは一万個近く落ちる結果になりました．線形合同法は，厳しい．
ちなみに，もっと意地悪をしてみようと思い，生成した乱数を bit reverse して BigCrush にかける，というテストも実行しましたが，結果はやはり殆ど変わりませんでした．（例えば，XSadd は普通に BigCrush すると通るものの，こうやって reverse すると落ちまくるらしい．）
表の数字をよく考えると分かる通り，実はメルセンヌ・ツイスターは正しく実装されていても BigCrush が結構落ちます．特に，必ず落ちるテストというのが 2 種類あって，それが 100 シード全部で落ちるのでそれだけで 200 個落ちてます．その点，最近の xorshift128+，xorshift1024* は，同様のテストを実行しても，落ちるテストは数十個みたいです．
BigCrush テストの出力も同リポジトリ内に置いてますので，詳しい結果が気になる方は直接ご覧ください．特に，seed = 12345678 で実行した結果は，上述の集計には入れてませんが，テストでよく使われている（例1, 例2）みたいなので置いてみました．最初に出力してる 16 個がそれら 2 つと一致しているので，壊れてる mt_rand・修正後の mt_rand 共に，公式と一致する実装が取り出せてると思います．
雑談：mt_rand が奇数しか生成しない（値域の指定によっては）
これはやや別の話題ですが，「PHP の mt_rand が奇数しか生成しない」という現象がやや前に報告されていました．ここで話題になっているコードを実行すると，確かに今でも奇数しか出てきません．これ，ヤバくないですか……？（というか，もしそうなら，何故 BigCrush に通るの……？）
これは実は，mt_rand の引数で値域が与えられた場合に，乱数生成器の出力を値域内に縮めたり広げたりする操作が，めちゃくちゃ雑に実装されていることが原因です．この RAND_RANGE 関数ですね．例えば，2 倍の範囲に広げる際，単純に 2 を掛けるという極めて雑な実装になっているので，偶奇が固定されてしまうんですね．RAND_RANGE は mt_rand だけじゃなくて rand でも使われてるので，そっちでも同じことが起こります．今回の BigCrush テストは値域の拡大縮小部分は対象外ですので，この点は結果に表れませんでしたが，値域を指定して使うのは要注意だと思います．
ちなみに，ドキュメントをよく読むと，「注意」のセクションにこの現象に関するものと思われる記述があります．
警告
64 ビット版の PHP で max を 2^32 より大きくすると、mt_rand() の返り値の分布にバイアスがかかり、偶数よりになります。 max が mt_getrandmax() の返り値より大きくなると、 乱数生成器の出力をスケールアップする必要があるからです。
http://php.net/manual/ja/function.mt-rand.php
ただし，そこには値域を拡大する際の警告のみが書かれていますが，この実装では原理的には値域の縮小の際にも偏りが起こるはずなので，ヤバいことが起きてる事案がこれまでにあっても不思議ではないと思います．
その点，例えば C++ の std::uniform_int_distribution は，libc++ でも libstdc++ でも，値域を拡大させる際はもちろん，縮小させる際にも必要に応じて乱数を複数使うように書かれていました．安心．
