TinyMTの更新を行列で書いてみようのコーナー(後編)

初めに

TinyMTの更新を行列で書いてみようのコーナー(前編) - yatsuna_827’s blogのつづき。前編では数式が盛り沢山だったせいで多数の数学アレルギー患者に急性発作を引き起こさせてしまいましたが、今回は1と・しか出てこないので比較的安全だと思います。

前回求めた行列

$$ \begin{align} \begin{bmatrix} {\boldsymbol s}'_{0} & {\boldsymbol s}'_{1} & {\boldsymbol s}'_{2} & {\boldsymbol s}'_{3} \end{bmatrix} = \begin{bmatrix} {\boldsymbol s}_{0} & {\boldsymbol s}_{1} & {\boldsymbol s}_{2} & {\boldsymbol s}_{3} \end{bmatrix} \begin{bmatrix} {\boldsymbol O} & U_{31}C_{mat1} & U_{31}(L'_{1}L'_{10}+ C_{mat2}) & U_{31} L'_{1} \\ I & C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & I+C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & (I + R_{1})C_{mat1} & R'_{1}L_{10} + R'_{1}C_{mat2} & R'_{1} \end{bmatrix} \end{align} $$
確認したところで、一列ずつ行きましょう。

1列目

零行列 ${\boldsymbol O}$ と単位行列 $I$ しか無いので特筆することは無いです。見やすいように0は・で表します。零行列は全部・なので割愛。単位行列は f:id:yatsuna_827:20171231173417p:plain
です。(こっちも言うまでも無いですが)

2列目

まず前編を書いた後で気づいたのですが、 $U_{31}C_{mat1} = C_{mat1}$ が成り立ちます。 $C_{mat1}$ は最下位bitのみに作用するので、最上位bitが欠落しようが何の関係も無いのです。なので、2列目の1行目と2行目はどちらも $C_{mat1}$ です。
mat1は0x8f7011eeで、2進数に直すと10001111011100000001000111101110となります。 $C_{mat1}$ はこれを最下段に並べた行列で、 f:id:yatsuna_827:20171231174059p:plain
となります。 $I + C_{mat1}$ はこれに単位行列を加えた行列で、 f:id:yatsuna_827:20171231174426p:plain
です。
そして $(I+R_{1})C_{mat1} = C_{mat1} + R_{1}C_{mat1}$ は、 $C_{mat1}$ に $R_{1}C_{mat1}$ を加えた行列です。
$R_{1}C_{mat1}$ は自信が無かったのでExcelくんに計算してもらいました。結果的には $C_{mat1}$ を右と上にそれぞれ1ずつずらした行列です。よって $(I+R_{1})C_{mat1} = C_{mat1} + R_{1}C_{mat1}$ は、 f:id:yatsuna_827:20171231175904p:plain
となります。

3列目

まずは $L'_{1}L'_{10}$ を展開しましょう。 $L_{n}L_{m} = L_{n+m}$ が成り立つので、括弧を展開すると $$ \begin{align} (I + L_{1})(I + L_{10}) &= I + L_{1} + L_{10} + L_{1}L_{10} \\ &= I + L_{1} + L_{10} + L_{11} \end{align} $$ となります。ただし、4行目の $R'_{1}L_{10}$ の展開は $R_{1}L_{10} = L_{9}$ は成り立たないので注意です。(押し出されたbitの情報が欠損するため。)
こちらは、
$$ \begin{align} (I + R_{1})L_{10} = L_{10} + R_{1}L_{10}
\end{align} $$ で終わりです。
また、 $U_{31}$ に $L_{n}$ を作用させると、自動的に最上位bitは押し出されて欠落するので、 $$ U_{31}L_{n}=L_{n} $$ が成り立ちます。

以上を踏まえると、3列目は1行目から順に $$ \begin{align} U_{31} + L_{1} + L_{10} + L_{11} + C_{mat2} \\ I + L_{1} + L_{10} + L_{11} + C_{mat2} \\ I + L_{1} + L_{10} + L_{11} + C_{mat2} \\ L_{10} + R_{1}L_{10} + C_{mat2} + R_{1}C_{mat2} \end{align} $$
となります。
$U_{31} + L_{1} + L_{10} + L_{11}$ は
f:id:yatsuna_827:20171231213341p:plain
という行列で、mat2の値はmat2 0xfc78ff1f(2進数で11111100011110001111111100011111)なので、 $C_{mat2}$ は
f:id:yatsuna_827:20171231213538p:plain
なので、1行目は
f:id:yatsuna_827:20171231213616p:plain
という行列になります。2行目、3行目はほぼ同じ行列で、(1,1)成分が1になっただけです。
f:id:yatsuna_827:20171231213729p:plain

4行目、 $L_{10} + R_{1}L_{10}$ は
f:id:yatsuna_827:20171231214959p:plain
です。よく見ると $R_{1}L_{10}$ と $L_{9}$ とは若干異なっているのがわかると思います。
$C_{mat2} + R_{1}C_{mat2}$ は
f:id:yatsuna_827:20171231215202p:plain
なので、4行目は
f:id:yatsuna_827:20171231215228p:plain
となります。

4列目

ほとんどまんまです。1行目は
$$ U_{31}(I + L_{1}) = U_{31} + L_{1} $$ なので、
f:id:yatsuna_827:20171231215959p:plain
2行目、3行目は $I + L_{1}$ で、
f:id:yatsuna_827:20171231220042p:plain
4行目は $I + R_{1}$ で、
f:id:yatsuna_827:20171231220112p:plain
です。

組み合わせる

これらの行列を並べると、前回求めた更新を表す行列ができあがります。
f:id:yatsuna_827:20171231220223p:plain
ワッショイ！

最後に

計算が苦手なので大変でした(小並感)。ですが、Excelを使うことで、計算が合っているかどうかを確かめながら作業を進めることができました。
線形代数の初めの方に出てくるクッソめんどくさい行列計算は、Excelを使うととても楽です。逆行列も求められます。ということで…

オマケ

Excelを使って、直接逆行列を求めてみました。
f:id:yatsuna_827:20171231220847p:plain

最後の最後に

前編を書き上げた後で計算ミスやら記述ミスやらが次々発覚してサイレント修正しながら後編を書きました。大晦日に。ガキ使見ながら。弟たちは友達の家に遊びに行っているというのに。。。
それは置いておくとして、本家MTも同様に624項をまとめて1つの内部状態 ${\boldsymbol x}_{n}$ とみなすことで、行列を用いて ${\boldsymbol x}_{n+1} = {\boldsymbol x}_{n}A$ と表せるので、誰かやってみてください。求める過程自体は、おそらくTinyMTよりも簡単だと思います。来年のAdvent Calenderのネタにどうでしょうか。
それではよいお年を。