ちょっとTemperingの話

本当は行列の計算を色々試してて気づいたんだけど

y = y >> 1;
y = y ^ (y >> 11);

と

y = y ^ (y >> 11);
y = y >> 1;

って、結果を見るとあまり差がないよね。

ほんの少し正確に書くと

word T1(word y) { return y ^ (y >> 11); }

って関数を考える。T1の逆関数をS1とする(簡単に作れるよね)。
こいつらは次の性質を持つ

T1(x ^ y) == T1(x) ^ T1(y)      (1)
T1(S1(x)) == S1(T1(x)) == x     (2)

まともな計算順序でやると

hi = mt[kk]&U;
lo = mt[kk+1]&L;
r = T1(mt[kk+M] ^ ((hi^lo) >> 1) ^ mag01[lo & 1]);

になるところを、(1)を駆使して

r = T1(mt[kk+M]) ^ T1(hi >> 1) ^ T1(lo >> 1) ^ T1(mag01[lo & 1]);

さっきの大体等しかったところを置き換えて

r ≒ T1(mt[kk+M]) ^ (T1(hi) >> 1) ^ (T1(lo) >> 1) ^ T1(mag01[S1(T1(lo)) & 1]);

hi = T1(mt[kk])&U;
lo = T1(mt[kk+1])&L;
r ≒ T1(mt[kk+M]) ^ ((hi^lo) >> 1) ^ T1(mag01[S1(lo) & 1]);

とかやってみると、mt[i]の代わりにT1(mt[i])を保存しといたほうがよさそうじゃん。

実際にはこんないい加減な議論じゃなくて、行列を掛けたり逆行列したりで真面目に計算して実装したんだけど、
上の計算で必要なXORが67から51に減ります。T1に必要な21回のXORが消滅して、調節用のXORが少し増えた結果です。