メルセンヌツイスタの調律を行列で書く
擬似乱数生成器メルセンヌツイスタ(MT)には以下のような調律(tempering)と呼ばれる関数が登場します。
u32 tempering(u32 x) {
x ^= (x >> 11);
x ^= (x << 7) & 0x9d2c5680;
x ^= (x << 15) & 0xefc60000;
x ^= (x >> 18);
return x;
}
MTの作者自身の講義ノートでtemperingはある行列をかけていることに相当することが書いてあります。
(引用した講義ノートでは横ベクトルに行列を右から掛けていますが、今回の記事では縦ベクトルに左から行列を掛けることにします)
実際にこの行列を求めてみました。行列Tは:
さらにこの行列の逆行列T^{-1}は
見やすさのために0はドットにしておきました。
説明図:
32-bitの整数は集合{0,1}の要素を成分とする32次元の(列)ベクトルと同一視できます。
{0,1}という集合に、通常の算術の和と積を2で割ったあまりとして和と積を定義しましょう。すると有理数全体や実数全体と同じような四則演算の法則が成り立ちます。つまり{0,1}はこの演算で体になるということです。この体をF_2と呼びます。
このとき整数のxorはベクトルの和に対応します。
そうすればx -> x xor (x >> 11)という関数がこんな行列に対応することが分かるはずです。
temperingのほかの行も同様に行列で書けます。それらの積をとれば最初の行列Tが得られます。
F_2が体となることが効いて、有理数を成分とする行列や実数を成分とする行列と同じように線形代数の理論が使えて逆行列も有理数などのときと同じ方法で求めることができます。
(ただ今回の場合はまず有理数で逆行列を求めてからそれをF_2の元に変換しました)
追記 (2014/10/23)
参考までにtemperingの逆関数は次のようになります。どうぞご利用ください。
u32 tempering_inv(u32 x) {
x ^= (x >> 18);
x ^= ((x << 15) & 0xefc60000);
x ^= ((x << 7) & 0x9d2c5680) ^ ((x << 14) & 0x94284000) ^ ((x << 21) & 0x14200000) ^ ((x << 28) & 0x10000000);
x ^= (x >> 11) ^ (x >> 22);
return x;
}
