メルセンヌ・ツイスタ
メルセンヌ・ツイスタ(Mersenne twister、通称MT)は1996年から1998年（1996年国際会議で発表、1997年朝日新聞記事、1998年1月論文掲載）に松本眞と西村拓士によって開発された擬似乱数生成器である。既存の乱数生成アルゴリズムの欠点を改良して、高品質の乱数を高速に生成するように設計されている。 2007年1月31日、松本眞とその指導学生の斎藤睦夫により、上記の改良版SFMTがウェブサイトに発表された。現在、公式ウェブサイトからダウンロードできる。
考案者らによる実装のライセンスは、公開当初GPLであったが、現在はBSDライセンスである。
目次 |
[編集] 長所
このアルゴリズムには二つのバージョンがあるが、最新のバージョンであり、広く使われているメルセンヌ・ツイスタはMT19937である。それには以下のような望ましい性質がある。
- 219937-1 という長い周期（この周期をもつことはアルゴリズムの作成者によって証明されている）。
- この周期は、名前の由来にもなっているように メルセンヌ素数であり、またこのアルゴリズムが保証するいくつかの特徴はメルセンヌ素数を内部的に使用していることによって達成されている。実際上、これ以上の長い周期の擬似乱数を使用する理由はない。
- 高次元（623次元）に均等分布する（線形合同法#短所参照）。
- このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。例えば、32bit版のメルセンヌ・ツイスタを複数回呼び出して64bit、128bitなどの乱数として利用しても統計的に安全である。
- 統計的に不適当な乱数しか生成しない擬似乱数ジェネレータを除けば、あらゆる擬似乱数生成法の中でもっとも速い（当時）。
- 近年、メルセンヌ・ツイスタより高速で、統計的にも問題の少ない乱数発生器も考え出されはじめている。とにかく高速な乱数ジェネレータが必要であれば、メルセンヌ・ツイスタ以外も検討すべきだろう。メルセンヌ・ツイスタの利点は長周期性と均等性にある（ただしCPUごとに最適化されたコードであれば、現時点でもメルセンヌ・ツイスタは十分に速い）。
- 出力の中のすべてのビットが統計的に十分ランダムである。
- メルセンヌ・ツイスタの前身GFSRはそうではなかった。以下に詳述
メルセンヌ・ツイスタのアルゴリズムは一般・フィードバック・シフト・レジスタ(General Feedback Shift Register)をひねって(Twisted)調律した(Tempered)もの（略してTTGFSR）である。GFSRではワード中の各ビットは独立していたが、「ひねる」ことによって各ビットの周期が合わさって長い周期を実現できるようになっている。「調律」は生成された乱数のワードのうち数ビットだけを取り出したときの高次元超立方体への均等分布を改良して理論値に近づけるための工夫である（メルセンヌ・ツイスタは「調律」がなくても623次元超立方体に均等分布する）。ここまでのアルゴリズムは先行するTT800と同様であるが、メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した（あるいは31ビット欠けた）形をしている点に特徴がある。これは19937÷32が623余り1であることによる。このような状態空間をとることによって219937-1という周期を実現している。
[編集] 短所
多くのアプリケーションにとって、メルセンヌ・ツイスタは優れた乱数生成法である。しかしながら、実際にプログラムで利用するにあたっては、いくつか留意すべき点がある。
- 暗号論的擬似乱数生成器ではない。
- メルセンヌ・ツイスタは線形漸化式によって生成されるため、予測可能である。暗号用途で利用するには暗号学的ハッシュ関数のような非可逆な操作を通すべきである。CryptMTやFubukiといったアルゴリズムはメルセンヌ・ツイスタをベースとしているが、単純にその出力を鍵ストリームとして平文と合成しているわけではない。
- 内部ベクトルが大きい
- メルセンヌ・ツイスタは内部に623個の32ビット長の状態ベクトルを持つ。
- 一般的な乱数発生器と比較してワーキングメモリが大きい。開発者による実装では32bit版で624ワード=2496バイトのワーキングメモリを要する。
- 第三者による高速化を狙った実装（並列計算を行うなど）では、より多くのワーキングメモリを要しているものが多い（例えば倍の4992バイトなど）。
- ベクトルを初期化するために19936ビット長の乱数が必要となることを意味している。開発者が公開しているコードでは、あまり初期化処理が良くないと言われている。
- 初期化のために別の乱数発生器（物理乱数や暗号論的乱数）を利用することで解決できる。
- （当然であるが）メルセンヌ・ツイスタを初期化するためにメルセンヌ・ツイスタを用いることはできない。一つのメルセンヌ・ツイスタと同じことだからである。
- 初期化のために別の乱数発生器（物理乱数や暗号論的乱数）を利用することで解決できる。
- もっとも、メルセンヌ・ツイスタ以前の「良い」乱数発生器はさらに大きなワーキングメモリを必要とするものがあり、メルセンヌ・ツイスタは比較的効率が高いと言える。
- 初期状態空間に0が多いと、しばらくの間出力にも0が多くなる。
- 線形フィードバックシフトレジスタに共通の問題点である。大きな配列の数箇所を参照して、1箇所を書き換えるため、全体を書き換えるのに時間がかかることと、状態遷移関数が線形であるために、参照した数箇所が全て0の場合、出力も0になるためである。
- 初期化処理で、状態空間に0が多くならないようにすればよい。
- オリジナルの初期化処理では問題とならないようである。独自の初期化処理を使用する場合には問題が発生する可能性がある。
- このため初期化直後に生成される乱数は、50～100万個ほど読み捨てた方が良いとする意見もある。
- この問題に関する改善をした乱数生成器にWELLなどがある。
なお、上記の欠点のうち、内部ベクトルの大きさや零超過状態からの回復速度の問題は、SIMD-oriented Fast Mersenne Twister (SFMT) で改善されている。
[編集] 余談
開発当初は Primitive Twisted Generalized Feedback Shift Register Sequence という名前であったが、クヌースに名前が長すぎると言われたため、現在の名前に変更された。
Mersenne Twister の MT には、開発者の名前「まこと」と「たくじ」のイニシャルという意味もこめられている。
http://www.soi.wide.ad.jp/class/20010000/slides/03/index_1.html の質疑応答部分のビデオ参照。
[編集] 参照
- M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.
[編集] 関連項目
- GNU Scientific Library (GSL, GSL ホームページ) はメルセンヌ・ツイスタの実装を含んでいる。
- R言語 - フリーウェアの数値解析言語。行列や時系列型のオブジェクトを備える。乱数方式のデフォルトがメルセンヌ・ツイスタ。多様な乱数方式関数も標準で備える。プログラム自動配信の仕組「CRAN」によって、さらに多くの乱数方式も利用することが出来る。マルチプラットフォーム。
- C++0x - C++03からTechnical Report 1を経て策定の進む次期C++標準ライブラリの<random>ではMT19937が標準の擬似乱数生成器として実装される。
