- 原著はこちら：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 を書いてみました：
- 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回しか合格しないケースがあることにびっくりです。
May 16, 2010
乱数生成アルゴリズム WELL
Mersenne Twister (MT) の作者らによる比較的新しいアルゴリズム・ WELL (Well Equidistributed Long-period Linear) についてのメモです。
Subscribe to:
Posts (Atom)