乱数生成アルゴリズム WELL

Mersenne Twister (MT) の作者らによる比較的新しいアルゴリズム・ WELL (Well Equidistributed Long-period Linear) についてのメモです。

• 原著はこちら：L'Ecuyer, Pierre; Panneton, François; Matsumoto, Makoto (2006), Improved Long-Period Generators Based on Linear Recurrences Modulo 2
• http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf
• 論文の訂正表はこちら。シフト演算の部分に関する誤りが訂正されているので必ず参考に。
• http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt
• Game Programming Gems 7 で紹介されています。記事を書いた Chris Lomont 氏 (http://www.lomont.org/) のサイトで原文が公開されています：
• http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
• アルゴリズムの特徴は：
• MTより計算が少しだけ重い。
• MTは初期状態のビットパターンに0を多く含んでいると、出力する乱数のビットパターンにもしばらく0が多く含まれてしまう傾向がある。WELLはこのような状態からの脱出がMTに比べて早い。
• C# (VS 2010) で周期 2^1024 バージョンの WELL を書いてみました：
• http://sites.google.com/site/ltsevenscore/archives/WELL-20100516.zip
• テストコードは Monobit テストを10000回実行して合格した回数を表示するものです。
• Monobit テスト： 20000ビット分の乱数に含まれる1の数が10000個から大きく離れていないかどうかをチェックする検定方法。
• 参考：http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf
• 10000回の Monobit テストに対して不合格となるのは1〜2回程度。優秀だと思います。
• System.Random を使ったら Monobit テスト 10000回に対して3000〜4000回しか合格しないケースがあることにびっくりです。