乱数ライブラリー

メルセンヌ・ツイスタ

メルセンヌ・ツイスタ(以下はMTと表記)はM系列を松本眞と西村拓士が発展させたものであり、疑似乱数生成器として現在最も高い評価を得ている。疑似乱数は主にコンピュータ上で生成・使用される。そのために生成される乱数の質や周期の長さと同等に、コンピュータ上で生成される速度、プログラミングの簡素さ、使用する記憶領域の大きさが乱数生成器の評価のポイントとなる。メルセンヌ・ツイスタはこれらが高いレベルでバランスがとれていることが、高い評価につながっている。

まずM系列を発展させたTwisted General Feedback Shift Register(以下はTGFSRと表記)が提案された。これは

x n + p = x n + q + x n A     ( p > q > 0 ) x_{n+p}=x_{n+q}+x_{n}A(p>q>0)


を用いて乱数列を生成する。ここで A A はTwisterと呼ばれる GF ( 2 ) GF(2) の元を要素とする ω× ω ω!underline {ω} の行列である。ただし x n GF ( 2 ) ω x_n in GF(2)^ω である。TGFSRはM系列と同様 ビットの記憶領域を使用し、 2 - 1 2^pω-1 の最大周期をもつ。M系列の最大周期は 2 p - 1 2^{p-1} であるから、TGFSRの方がこの点で優れている。また計算が高速になるような A A を選択することができるため、乱数列の生成速度はM系列とほぼ同等である。

TGFSRを改良したものがメルセンヌ・ツイスタである。これは以下により乱数列を生成する。

x n + p = x n + q + x n + 1 B + x n C     ( p > q > 0 ) x_{n+p}=x_{n+q}+x_{n+1}B+x_{n}C(p>q>0)


式(2)による最大周期が 2 19937 - 1 2^{19937}-1 のとき、特にMT19937と呼ばれる。通常MTはMT19937を指す。

以下で線形合同法及びM系列の短所を挙げ、次にMTの長所を挙げることによってMTの高い評価の理由を示す。

まず線形合同法の短所として、周期が短いことが挙げられる。周期が M M 以上にならず、大量の乱数列を使用するシミュレーションでは用いることができない。次に下位ビットのランダム性が低い。 M M を偶数にした場合、下位ビットにおいて0か1が続けて出るか、0と1が交互に出現する現象が現れる。また致命的な欠点として、多次元で均等分布しない性質がある。これは乗数 a a について良い選択をしないと、下位ビットにおいて周期性(多次元結晶構造)が現れることを表している。

M系列の短所としては、線形合同法より改良されてはいるものの、最大周期は 2 p - 1 2^{p}-1 にとどまり、やはり大量の乱数列を使用するシミュレーションでは十分であるとは言えない。次に出力されたすべてのビットが統計的に十分にランダムでない。また初期値の設定について良い選択をしないと質の悪い乱数が生成されることが挙げられる。

以上に対しMTは 2 - 1 2^pω-1 の最大周期が証明されている。また高次元に均等分布し、連続で出力された乱数列間に相関が無いものとして乱数列を扱うことができる。出力されたすべてのビットが統計的に十分にランダムである。これらの理由により、MTは乱数生成機として最も高い評価を得ている。




▲このページのトップに戻る