メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。従来の疑似乱数列生成手法にある多くの欠点を克服し、高品質の疑似乱数列を高速に生成できるものとして、1996年に松本眞と西村拓士によって国際会議で発表された（1998年1月に論文掲載）。考案者らによる実装が修正BSDライセンスで公開されている。
特徴 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式（あるいは生成法）の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 長所 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように（24番目の）メルセンヌ素数であり、保証されているいくつかの特徴はメルセンヌ素数を内部的に使用していることによって達成されている。実用上は、これ以上の長い周期を持つ擬似乱数が必要になることはないであろう。 高次元（623次元）に均等分布する（線形合同法#短所参照）。 このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。例えば、32ビット版のメルセンヌ・ツイスタを複数回呼び出して64ビット、128ビットなどの疑似乱数として利用しても統計的に安全である。 あらゆる擬似乱数列の生成法のうちで統計的に不適当なものを除外して比較すると最も速い（当時）。 近年では、統計的な問題点が少なく、メルセンヌ・ツイスタよりも高速な擬似乱数列の生成器がいくつか考案されている。疑似乱数の生成速度を優先する場合には、それらの生成器が役に立つ可能性がある。メルセンヌ・ツイスタの利点は、長い周期と均等性、および既に広範に使われて実証済みであることである（ただしCPUごとに最適化されたコードであれば、現時点でもメルセンヌ・ツイスタは十分に速い）。 出力の中のすべてのビットが統計的に十分ランダムである。 メルセンヌ・ツイスタの前身のGFSRではそうではなかった。以下に詳述
メルセンヌ・ツイスタの手法を、以前の生成法に関連付けて表現すると、一般・フィードバック・シフト・レジスタ (General Feedback Shift Register) をひねって (Twisted) 調整した (Tempered) もの（略してTTGFSR）となる（実際に、元はそのように呼んでいた）。GFSRではワード中の各ビットは独立していたが、「ひねる」ことによって各ビットの周期が合わさって長い周期を実現できるようになっている。「調整」は生成された疑似乱数のワードのうち数ビットだけを取り出したときの高次元超立方体への均等分布を改良して理論値に近づけるための工夫である（メルセンヌ・ツイスタは「調整」をしなくても623次元超立方体に均等分布する）。ここまでは先行するTT800と同様であるが、メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した（あるいは31ビット欠けた）形をしている点に特徴がある。これは19937÷32が623余り1であることによる。このような状態空間を採択することによって周期 219937-1 を実現している。
短所 多くのアプリケーションにとって、メルセンヌ・ツイスタは優れた疑似乱数生成法である。しかしながら、実際にプログラムで利用するにあたっては、いくつか留意すべき点がある。
暗号論的擬似乱数列生成器 (CSPRNG) ではない。 メルセンヌ・ツイスタは線形漸化式によって生成されるため、他の一般の疑似乱数生成法と同様に予測可能である。従って暗号用途で利用するには同様に、暗号学的ハッシュ関数のような非可逆な操作を通さなければならない。やFubukiはメルセンヌ・ツイスタをベースとしているが、単純にその出力を鍵ストリームとして平文と合成しているわけではない。 内部ベクトルが大きい メルセンヌ・ツイスタは内部に623個の32ビット長の状態ベクトルを持つ。つまり、一般的な擬似乱数列生成器と比較して動作に必要なメモリ量（ワーキングメモリ）が大きい。開発者による実装では32ビット版で624ワード（2496バイト）のワーキングメモリを要する。 第三者による高速化を狙った実装（並列計算を行うなど）は、より多くのワーキングメモリを要する（例えば倍の4992バイトなど）。 内部ベクトルを初期化するシード（乱数種）として19936ビットという長い乱数が必要となるため、シードや物理乱数を擬似乱数や暗号学的ハッシュ関数で伸長し、場合によってはさらにシードや物理乱数でベクトルを撹拌することでこの問題と後述する0の量を解決する必要がある。 （当然であるが）メルセンヌ・ツイスタを初期化する擬似乱数にメルセンヌ・ツイスタを用いることはできない。初期化に使用するメルセンヌ・ツイスタを初期化する長いベクトルが用意できないからである。 開発者が公開しているコードでは、単一の32ビット値からなるシードを用いた別の擬似乱数による初期化処理と、固定値で初期化したベクトルを任意個数の32ビット値からなる初期化鍵で撹拌する初期化処理が実装されている。 短い乱数や時刻情報を元に初期化したメルセンヌ・ツイスタはその出力を調べることでシードを推測できる可能性が指摘されているなど、初期化に使用する情報量が少ない場合、問題が生じる場合がある。 もっとも、メルセンヌ・ツイスタ以前の「良い」擬似乱数列生成器はさらに大きなワーキングメモリを必要とするものがあるため、メルセンヌ・ツイスタは比較的効率が高いと言える。 初期状態空間に0が多いと、しばらくの間出力にも0が多くなる。 これは線形フィードバックシフトレジスタに共通する問題点である。この原因は、大きな配列の数か所を参照して1か所を書き換えるため、全体を書き換えるのに時間がかかることと、状態遷移関数が線形であるために、参照した数か所が全て0の場合、出力も0になるためである。 初期化処理で、状態空間に0が多くならないようにすればよい。 考案者らが提供している実装では、初期化に内部状態空間の小さな擬似乱数生成系を利用しているので（その小ささゆえに、全て0といったような列は生成し得ないので）これは問題とならない。独自の初期化処理を使用する場合には問題が発生する可能性がある。 この問題に関する改善をした擬似乱数列生成器にWELLなどがある。
なお、上記の欠点のうち、内部ベクトルの大きさや零超過状態からの回復速度の問題は、SIMD-oriented Fast Mersenne Twister (SFMT) で改善されている。
各種プログラミング言語におけるライブラリ 一部のプログラミング言語では、デフォルトの擬似乱数列生成器としてメルセンヌ・ツイスタが標準ライブラリに取り入れられている。そのような言語の例として、 Python, Ruby, R, PHP, MATLAB, C++（C++11から） がある。
その他のプログラミング言語におけるライブラリの例として、以下が挙げられる：
：ABAP ：ActionScript 1 AS3-UtilitiesAS3-Utilities/Random.as at master · skyboy/AS3-Utilities · GitHub：ActionScript 3.0 ：Ada Pseudo random number generators：C++ Mersenne Twist PRNG：C and C++ ：C++ RandomLibRandomLib：C++ Mersenne Twister in ClojureMersenne Twister in Clojure – hackinghat.com：Clojure ：Clean ：C++ Sony Cell Broadband Engine ：C# jmt.lisp : Common Lisp random.dphobos/random.d at master · dlang/phobos · GitHub：D sfmt-erlangGitHub - jj1bdx/sfmt-erlang: sfmt-erlang: SIMD-oriented Fast Mersenne Twister (SFMT) for Erlang：Erlang MT.Emt.zip：Euphoria NtRandExcel Random Generator based on Mersenne Twister - NtRand：Excel addin ：Forth ：Fortran 95 Mersenne TwisterMersenne Twister - Pastebin.com：F# GNU Scientific LibraryGSL - GNU Scientific Library - GNU Project - Free Software Foundation ：Haskell mersenne-random-pure64mersenne-random-pure64: Generate high quality pseudorandom numbers purely using a Mersenne Twister：Haskell MersenneTwister.javaSean Luke : Code：Java Mersenne Twister in Java ScriptMersenne Twister in Java Script：JavaScript mersenne-twister.jsa Mersenne Twister implementation in javascript. Makes up for Math.random() not letting you specify a seed value. · GitHub：JavaScript lrandomLuiz Henrique de Figueiredo: Libraries and tools for Lua：Lua ：Mitrion-C ：Pascal/FreePascal/Delphi Math-Random-MT-AutoSearch for "module:Math::Random::MT::Auto" - metacpan.org：Perl mersenne_twister.phpPure-PHP Mersenne Twister：PHP 5.3.0 Random Number GenerationR: Random Number Generation：R Mersenne twister in REALbasicMersenne twister：REALbasic ：Standard ML ：SIMUL8 MersenneTwister.scalaMersenne Twister - Random number generator · GitHub：Scala ：VBA Mersenne Twister in BASICMersenne Twister in BASIC：Visual Basic
名称の由来 開発当初は Primitive Twisted Generalized Feedback Shift Register Sequence という名前であったが、ドナルド・クヌースに「舌を噛みそうな名前だ」と言われたため、現在の名前に変更した。Mersenne Twister の略称 MT には、開発者の名前「まこと」と「たくじ」のイニシャルという意味もこめられている。
注釈
出典
参照 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が擬似乱数列生成器として実装される。 64ビット最適均等分布F2-線形発生法 - 上位ビットの高次元均等分布性が完全に最適化された64ビットメルセンヌ・ツイスタ型擬似乱数発生器が開発されている。
外部リンク Mersenne Twister: A random number generator (since 1997/10)：メルセンヌツイスターホームページ Another paper on the Mersenne Twister algorithm A claimed implementation of the Mersenne Twister algorithm 有限体の擬似乱数への応用 松本眞さんの擬似乱数発生法について Microsoft Excel 用メルセンヌツイスターによる乱数生成アドインソフト
松本眞：「あなたの使っている乱数、大丈夫？-危ない標準乱数と、メルセンヌ・ツイスター開発秘話-」（第50回市村学術賞記念先端技術講演会、2014年11月18日）