May 16, 2010

乱数生成アルゴリズム 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
  • 論文の訂正表はこちら。シフト演算の部分に関する誤りが訂正されているので必ず参考に。
  • Game Programming Gems 7 で紹介されています。記事を書いた Chris Lomont 氏 (http://www.lomont.org/) のサイトで原文が公開されています:
  • アルゴリズムの特徴は:
    • MTより計算が少しだけ重い。
    • MTは初期状態のビットパターンに0を多く含んでいると、出力する乱数のビットパターンにもしばらく0が多く含まれてしまう傾向がある。WELLはこのような状態からの脱出がMTに比べて早い。
  • C# (VS 2010) で周期 2^1024 バージョンの WELL を書いてみました:
  • 10000回の Monobit テストに対して不合格となるのは1〜2回程度。優秀だと思います。
    • System.Random を使ったら Monobit テスト 10000回に対して3000〜4000回しか合格しないケースがあることにびっくりです。