メルセンヌ・ツイスタ

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数生成器 (PRNG) の1つである。1996年から1998年（1996年国際会議で発表、1997年朝日新聞記事、1998年1月論文掲載）に松本眞と西村拓士によって開発された。既存の疑似乱数生成アルゴリズムの欠点を改良して、高品質の疑似乱数を高速に生成するように設計されている。 2007年1月31日、松本眞とその指導学生の斎藤睦夫により、上記の改良版SFMTがウェブサイトに発表された。現在、公式ウェブサイトからダウンロードできる。

考案者らによる実装はBSDライセンスで公開されている。公開当初はGPLで公開されていた。

長所

このアルゴリズムには二つのバージョンがあるが、最新のバージョンであり、広く使われているメルセンヌ・ツイスタはMT19937である。それには以下のような望ましい性質がある。

  1. 219937-1 という長い周期（この周期をもつことはアルゴリズムの作成者によって証明されている）。
    • この周期は、名前の由来にもなっているように メルセンヌ素数であり、またこのアルゴリズムが保証するいくつかの特徴はメルセンヌ素数を内部的に使用していることによって達成されている。実際上、これ以上の長い周期の擬似乱数を使用する理由はない。
  2. 高次元（623次元）に均等分布する（線形合同法#短所参照）。
    • このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。例えば、32bit版のメルセンヌ・ツイスタを複数回呼び出して64bit、128bitなどの疑似乱数として利用しても統計的に安全である。
  3. 統計的に不適当な疑似乱数しか生成しない擬似乱数生成器を除けば、あらゆる擬似乱数生成法の中でもっとも速い（当時）。
    • 近年、統計的な問題が少なく、メルセンヌ・ツイスタよりも高速な疑似乱数生成器がいくつか考案されている。疑似乱数の生成速度を優先する場合は、これらの生成器が役に立つ可能性がある。メルセンヌ・ツイスタの利点は、長周期性と均等性、および既に広範に使われテストされていることである（ただしCPUごとに最適化されたコードであれば、現時点でもメルセンヌ・ツイスタは十分に速いテンプレート:要出典）。
  4. 出力の中のすべてのビットが統計的に十分ランダムである。
    • メルセンヌ・ツイスタの前身GFSRはそうではなかった。以下に詳述

メルセンヌ・ツイスタのアルゴリズムは一般・フィードバック・シフト・レジスタ(General Feedback Shift Register)をひねって(Twisted)調律した(Tempered)もの（略してTTGFSR）である。GFSRではワード中の各ビットは独立していたが、「ひねる」ことによって各ビットの周期が合わさって長い周期を実現できるようになっている。「調律」は生成された疑似乱数のワードのうち数ビットだけを取り出したときの高次元超立方体への均等分布を改良して理論値に近づけるための工夫である（メルセンヌ・ツイスタは「調律」がなくても623次元超立方体に均等分布する）。ここまでのアルゴリズムは先行するTT800と同様であるが、メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した（あるいは31ビット欠けた）形をしている点に特徴がある。これは19937÷32が623余り1であることによる。このような状態空間をとることによって219937-1という周期を実現している。

短所

多くのアプリケーションにとって、メルセンヌ・ツイスタは優れた疑似乱数生成法である。しかしながら、実際にプログラムで利用するにあたっては、いくつか留意すべき点がある。

  1. 暗号論的擬似乱数生成器 (CSPRNG) ではない。
    • メルセンヌ・ツイスタは線形漸化式によって生成されるため予測可能である。暗号用途で利用するには暗号学的ハッシュ関数のような非可逆な操作を通すべきである。CryptMTやFubukiといったアルゴリズムはメルセンヌ・ツイスタをベースとしているが、単純にその出力を鍵ストリームとして平文と合成しているわけではない。
  2. 内部ベクトルが大きい
    • メルセンヌ・ツイスタは内部に623個の32ビット長の状態ベクトルを持つ。つまり、一般的な疑似乱数生成器と比較して動作に必要なメモリ量（ワーキングメモリ）が大きい。開発者による実装では32bit版で624ワード=2496バイトのワーキングメモリを要する。
    • 第三者による高速化を狙った実装（並列計算を行うなど）は、より多くのワーキングメモリを要する（例えば倍の4992バイトなど）。
    • 内部ベクトルを初期化するシード（乱数種）として19936ビットという長い乱数が必要となるため、シードや物理乱数を擬似乱数や暗号学的ハッシュ関数で伸長し、場合によってはさらにシードや物理乱数でベクトルを撹拌することでこの問題と後述する0の量を解決する必要がある。
      • （当然であるが）メルセンヌ・ツイスタを初期化する擬似乱数にメルセンヌ・ツイスタを用いることはできない。初期化に使用するメルセンヌ・ツイスタを初期化する長いベクトルが用意できないからである。
      • 開発者が公開しているコードでは、単一の32ビット値からなるシードを用いた別の擬似乱数による初期化処理と、固定値で初期化したベクトルを任意個数の32ビット値からなる初期化鍵で撹拌する初期化処理が実装されている。
      • 短い乱数や時刻情報を元に初期化したメルセンヌ・ツイスタはその出力を調べる事でシードを推測できる可能性が指摘されている[1]など、初期化に使用する情報量が少ない場合、問題が生じる場合がある。
    • もっとも、メルセンヌ・ツイスタ以前の「良い」疑似乱数生成器はさらに大きなワーキングメモリを必要とするものがあるため、メルセンヌ・ツイスタは比較的効率が高いと言える。
  3. 初期状態空間に0が多いと、しばらくの間出力にも0が多くなる。
    • これは線形フィードバックシフトレジスタに共通する問題点である。この原因は、大きな配列の数箇所を参照して1箇所を書き換えるため、全体を書き換えるのに時間がかかることと、状態遷移関数が線形であるために、参照した数箇所が全て0の場合、出力も0になるためである。
    • 初期化処理で、状態空間に0が多くならないようにすればよい。
      • オリジナルの初期化処理では、これは問題とならないようであるテンプレート:要出典。独自の初期化処理を使用する場合には問題が発生する可能性がある。
    • この問題に関する改善をした疑似乱数生成器にWELLなどがある。

なお、上記の欠点のうち、内部ベクトルの大きさや零超過状態からの回復速度の問題は、SIMD-oriented Fast Mersenne Twister (SFMT) で改善されている。

各種プログラミング言語におけるライブラリ

一部のプログラミング言語では、デフォルトの疑似乱数生成器としてメルセンヌ・ツイスタが標準ライブラリに取り入れられている。そのような言語の例として、 Python,[2][3] Ruby,[4] R,[5] PHP,[6] MATLAB, C++[7]（C++11から） がある。

その他のプログラミング言語におけるライブラリの例として、以下が挙げられる：

余談

開発当初は Primitive Twisted Generalized Feedback Shift Register Sequence という名前であったが、理論計算機科学者のドナルド・クヌースに「名前が長すぎる」と言われたため、現在の名前に変更された。

Mersenne Twister の略称 MT には、開発者の名前「まこと」と「たくじ」のイニシャルという意味もこめられている。[2] の動画の質疑応答部分を参照。

脚注

テンプレート:脚注ヘルプ

  1. ↑ [1]
  2. ↑ テンプレート:Cite web
  3. ↑ テンプレート:Cite web
  4. ↑ テンプレート:Cite web
  5. ↑ テンプレート:Cite web
  6. ↑ テンプレート:Cite web
  7. ↑ テンプレート:Cite web

参照

  • 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++11 - 策定が進む次期C++標準ライブラリの<random>では、MT19937が標準の擬似乱数生成器として実装される。

外部リンク

「http://wikippe.e-do-match.com/index.php?title=メルセンヌ・ツイスタ&oldid=44564」から取得