# TinyMTの逆関数

## tl;dr
- おおむねは[おだんさんの記事](https://odanpoyo.github.io/2016/12/10/ciww1kld100002xu9c327eevp/)の通り。
- この記事で付け加えたいのは以下の2点
- $A^{-1}$と$B^{-1}$を行列を使わずに書くどうなるか
- 上記の考察には不十分な点があり、逆関数になっていない

## $A^{-1}$と$B^{-1}$をビット演算だけで行う
- 一般に`y = x ^ (x << n)`に対して`(y >> n) ^ (y >> (n-1)) ^ ... ^ (y >> 1)`で復元ができる。右シフトも同様。
- これは`for (i=1; i<32-n; i*=2) y = y << i`でより効率的に計算することができる。

## 逆関数になっていないことについて
- TinyMTはS0の最上位bitが遷移関数内で捨てられており、実際は状態ベクトルは127次元しかない
- 記事ではS1の復元を`ps1 = s0`として逆算を行っているが、実際はこれでは最上位bitの情報が復元されていない。
- `x`と`s2`まで復元できたら、`ps1 = s0`とする代わりに`ps1 = (s0 & 0x7FFFFFFF) ^ ((x ^ s2) & 0x80000000)`とすれば、S1が完全に復元できる（つまり最上位bitはS0ではなく`x ^ s2`の最上位bitを使う）。
- 行列表現を作って逆行列を直接求める場合も、S0の最上位bitを削って127次元に落としてから逆行列を求めないと、S0の最上位bitを復元に使っている逆行列が得られてしまう場合があるので注意が必要。