Toom-Cook 乗算法

概説

多倍長整数同士の乗算において、被乗数・乗数を ある程度大きな桁数(基数\(x\)) で分割した \(l\)次・\(m\)次多項式 とみなし、多項式同士の乗算を行う。（改めて多項式乗算の積に基数\(x\)を代入し、繰り上がりの正規化を行えば多倍長整数の積が求められる）

この時、多項式係数同士の乗算回数を \((l+m+1)\) に抑える方法を検討する。(基数\(x\)が充分に大きければ、伴って発生する加減算・定数乗除算の計算量は少ないとみなす)

\(\{A_i\},\{B_j\},\{C_k\}\) をそれぞれ被乗数・乗数・多項式乗算の積、の係数列とする。

\[ \left( A_i = \begin{cases} \mbox{(any)} & (0 \le i \le l) \\ 0 & (i \lt 0, l \lt i) \end{cases},\ B_j = \begin{cases} \mbox{(any)} & (0 \le j \le m) \\ 0 & (j \lt 0, m \lt j) \end{cases},\ C_k = \sum_{i=0}^{k} A_{i}B_{k-i} \right) \]

\[ \begin{align*} &\ \quad(A_lx^l+A_{l-1}x^{l-1}+\cdots +A_1x+A_0)(B_mx^m+B_{m-1}x^{m-1}+\cdots +B_1x+B_0)\\ &=A_lB_mx^{l+m}+(A_lB_{m-1}+A_{l-1}B_m)x^{l+m-1}+\cdots +(A_1B_0+A_0B_1)x+A_0B_0\\ &=C_{l+m}x^{l+m}+C_{l+m-1}x^{l+m-1}+\cdots +C_1x+C_0\\ &=\Biggl(\sum_{i=0}^lA_ix^i\Biggr)\Biggl(\sum_{j=0}^mB_jx^j\Biggr)=\sum_{k=0}^{l+m}\Biggl(\sum_{i+j=k}A_iB_j\Biggr)x^k=\sum_{k=0}^{l+m}\Biggl(\sum_{i=0}^{k}A_{i}B_{k-i}\Biggr)x^k=\sum_{k=0}^{l+m}C_kx^k \end{align*} \]

\((\sum_{i=0}^lA_ix^i),(\sum_{j=0}^mB_jx^j),(\sum_{k=0}^{l+m}C_kx^k)\) に整数の組 \((n,d)\) を用いて \(x=n/d\) と代入し、それぞれ \(d^l,d^m,d^{l+m}\) を乗じた値 \(\mathcal{A}(n/d),\mathcal{B}(n/d),\mathcal{C}(n/d)\) を考えると（ \(n/d\) は整数比を示す為の便宜上の表記、実質的には2変数の関数? \(1/0\) は \(\infty\) と表記 ）

\[ \mathcal{A}(n/d) = d^l \sum_{i=0}^l A_i (n/d)^i = \sum_{i=0}^l A_i n^i d^{l-i} = A_l n^l + A_{l-1} n^{l-1} d + \cdots + A_i n^i d^{l-i} +\cdots+ A_1 n d^{l-1} + A_0 d^l \]

\[ \mathcal{B}(n/d) = d^m \sum_{j=0}^m B_j (n/d)^j = \sum_{j=0}^m B_j n^j d^{m-j} = B_m n^m + B_{m-1} n^{m-1} d + \cdots + B_j n^j d^{m-j} + \cdots + B_1 n d^{m-1} + B_0 d^m \]

\[ \mathcal{C}(n/d) = d^{l+m} \sum_{k=0}^{l+m} C_k (n/d)^k = \sum_{k=0}^{l+m} C_k n^k d^{l+m-k} = \left( d^l \sum_{i=0}^l A_i (n/d)^i \right) \left( d^m \sum_{j=0}^m B_j (n/d)^j \right) = \mathcal{A}(n/d) \times \mathcal{B}(n/d) \]

\((l+m+1)\) 個の異なる整数比の組 \(\{(n_0,d_0),(n_1,d_1),\dots,(n_{l+m},d_{l+m})\}\) \([\forall p,q \in \{0,1,\dots,l+m\} ; p \neq q \to n_pd_q \neq n_qd_p]\) を用意し、下記のように逆行列を求める。

\[ \begin{bmatrix}\mathcal{A}(n_{l+m}/d_{l+m})\\\vdots\\\mathcal{A}(n_1/d_1)\\\mathcal{A}(n_0/d_0)\end{bmatrix} =\begin{bmatrix}(n_{l+m})^l&(n_{l+m})^{l-1}(d_{l+m})&\cdots&(n_{l+m})(d_{l+m})^{l-1}&(d_{l+m})^l\\\vdots&\vdots&\ddots&\vdots&\vdots\\(n_1)^l&(n_1)^{l-1}(d_1)&\cdots&(n_1)(d_1)^{l-1}&(d_1)^l\\(n_0)^l&(n_0)^{l-1}(d_0)&\cdots&(n_0)(d_0)^{l-1}&(d_0)^l\end{bmatrix} \begin{bmatrix}A_{l}\\\vdots\\A_1\\A_0\end{bmatrix}\tag{1} \]

\[ \begin{bmatrix}\mathcal{B}(n_{l+m}/d_{l+m})\\\vdots\\\mathcal{B}(n_1/d_1)\\\mathcal{B}(n_0/d_0)\end{bmatrix} =\begin{bmatrix}(n_{l+m})^m&(n_{l+m})^{m-1}(d_{l+m})&\cdots&(n_{l+m})(d_{l+m})^{m-1}&(d_{l+m})^m\\\vdots&\vdots&\ddots&\vdots&\vdots\\(n_1)^m&(n_1)^{m-1}(d_1)&\cdots&(n_1)(d_1)^{m-1}&(d_1)^m\\(n_0)^m&(n_0)^{m-1}(d_0)&\cdots&(n_0)(d_0)^{m-1}&(d_0)^m\end{bmatrix} \begin{bmatrix}B_{m}\\\vdots\\B_1\\B_0\end{bmatrix}\tag{2} \]

\[ \begin{bmatrix}\mathcal{A}(n_{l+m}/d_{l+m})\times\mathcal{B}(n_{l+m}/d_{l+m})\\\vdots\\\mathcal{A}(n_1/d_1)\times\mathcal{B}(n_1/d_1)\\\mathcal{A}(n_0/d_0)\times\mathcal{B}(n_0/d_0)\end{bmatrix} =\begin{bmatrix}(n_{l+m})^{l+m}&(n_{l+m})^{l+m-1}(d_{l+m})&\cdots&(n_{l+m})(d_{l+m})^{l+m-1}&(d_{l+m})^{l+m}\\\vdots&\vdots&\ddots&\vdots&\vdots\\(n_1)^{l+m}&(n_1)^{l+m-1}(d_1)&\cdots&(n_1)(d_1)^{l+m-1}&(d_1)^{l+m}\\(n_0)^{l+m}&(n_0)^{l+m-1}(d_0)&\cdots&(n_0)(d_0)^{l+m-1}&(d_0)^{l+m}\end{bmatrix} \begin{bmatrix}C_{l+m}\\\vdots\\C_1\\C_0\end{bmatrix} \]

\[ \begin{bmatrix}C_{l+m}\\\vdots\\C_1\\C_0\end{bmatrix} =\left(\begin{bmatrix}(n_{l+m})^{l+m}&(n_{l+m})^{l+m-1}(d_{l+m})&\cdots&(n_{l+m})(d_{l+m})^{l+m-1}&(d_{l+m})^{l+m}\\\vdots&\vdots&\ddots&\vdots&\vdots\\(n_1)^{l+m}&(n_1)^{l+m-1}(d_1)&\cdots&(n_1)(d_1)^{l+m-1}&(d_1)^{l+m}\\(n_0)^{l+m}&(n_0)^{l+m-1}(d_0)&\cdots&(n_0)(d_0)^{l+m-1}&(d_0)^{l+m}\end{bmatrix}^{-1}\right) \begin{bmatrix}\mathcal{A}(n_{l+m}/d_{l+m})\times\mathcal{B}(n_{l+m}/d_{l+m})\\\vdots\\\mathcal{A}(n_1/d_1)\times\mathcal{B}(n_1/d_1)\\\mathcal{A}(n_0/d_0)\times\mathcal{B}(n_0/d_0)\end{bmatrix}\tag{3} \]

よって、 \(\{(n_0,d_0),(n_1,d_1),\dots,(n_{l+m},d_{l+m})\}\) の組から逆行列をあらかじめ求めておき、式\((1),(2),(3)\)の計算をそれぞれ行うと、\(\{A_i\},\{B_j\}\)から\(\{C_k\}\)を求められる事になる。

参照

再帰的適用による漸近的な計算コスト

おおむね、上の物ほど小さな桁数での計算コストが小さく、下の物ほど大きな桁数での計算コストが小さくなる。

係数例