トゥーム・クック乗算

Toom- kでは、因子をk 個の部分に分割します。

最初のステップは、基数B  = b ⁱを選択することです。基数Bにおけるmとnの桁数がどちらも最大でk 桁（例えば、Toom-3 では 3 桁）になるようにします。iの典型的な選択例は次のとおりです。 

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}$

この例ではToom-3を実行するので、B = b ² = 10 ⁸を選択します。次に、 mとnを基数Bの数字m _i、n _iに分けます。

${\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}$

次に、これらの数字を次数( k − 1)の多項式pとqの係数として使用します。ただし、 p ( B )  = mおよびq ( B ) = nという性質を持ちます。   

${\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,}$

${\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,}$

これらの多項式を定義する目的は、それらの積r ( x ) = p ( x ) q ( x )を計算できれば、答えはr ( B ) = m × nになるということです。

乗算される数値の大きさが異なる場合、mとnに対して異なるk値（ k _mとk _nと呼ぶ）を使用すると便利です。例えば、アルゴリズム「Toom-2.5」は、k _m = 3、k _n = 2のToom-Cookアルゴリズムを指します。この場合、B = b ⁱのiは通常、次のように選択されます。      

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}$

多項式積を計算するためのトゥーム・クック法${\displaystyle p(x)q(x)}$はよく使われるものです。次数 の多項式であることに注意してください。${\displaystyle d}$は、${\displaystyle d+1}$点（例えば、直線 – 1次の多項式は2つの点で指定される）。アイデアは評価することである。${\displaystyle p(\cdot )}$そして${\displaystyle q(\cdot )}$様々な点における値を求めます。次に、これらの点における値を掛け合わせて、積多項式上の点を求めます。最後に、補間によって係数を求めます。

以来${\displaystyle \deg(pq)=\deg(p)+\deg(q)}$必要になる${\displaystyle \deg(p)+\deg(q)+1=k_{m}+k_{n}-1}$最終結果を決定するポイント。これを${\displaystyle d}$Toom-3の場合、${\displaystyle d=5}$アルゴリズムは、どの点を選択しても機能します（いくつかの小さな例外を除きます。補間における行列の可逆性の要件を参照してください）。ただし、アルゴリズムを簡略化するために、0、1、-1、-2 のような小さな整数値を選択するのが望ましいです。

よく使われる珍しい点値の 1 つは無限大で、${\displaystyle \infty }$または${\displaystyle 1/0}$多項式を「評価」するには${\displaystyle p}$無限大では、実際には極限を取ることを意味します${\displaystyle p(x)/x^{\deg p}}$として${\displaystyle x}$無限大に及ぶ。したがって、${\displaystyle p(\infty )}$は常にその最高次係数の値です（上記の例では係数${\displaystyle m_{2}}$)

Toom-3の例では、ポイントを使用します${\displaystyle 0}$、${\displaystyle 1}$、${\displaystyle -1}$、${\displaystyle -2}$、 そして${\displaystyle \infty }$これらの選択により評価が簡素化され、以下の式が得られます。

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}$

そして同様に${\displaystyle q}$この例では、得られる値は次のとおりです。

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}&=&56789012&=&56789012\\p(1)&=&m_{0}+m_{1}+m_{2}&=&56789012+78901234+123456&=&135813702\\p(-1)&=&m_{0}-m_{1}+m_{2}&=&56789012-78901234+123456&=&-21988766\\p(-2)&=&m_{0}-2m_{1}+4m_{2}&=&56789012-2\times 78901234+4\times 123456&=&-100519632\\p(\infty )&=&m_{2}&=&123456&=&123456\\[4pt]q(0)&=&n_{0}&=&54321098&=&54321098\\q(1)&=&n_{0}+n_{1}+n_{2}&=&54321098+43219876+98765&=&97639739\\q(-1)&=&n_{0}-n_{1}+n_{2}&=&54321098-43219876+98765&=&11199987\\q(-2)&=&n_{0}-2n_{1}+4n_{2}&=&54321098-2\times 43219876+4\times 98765&=&-31723594\\q(\infty )&=&n_{2}&=&98765&=&98765\end{array}}}$

図に示すように、これらの値は負の値になる場合があります。

後々の説明のために、この評価プロセスを行列とベクトルの乗算として捉えると便利だろう。行列の各行には評価点の1つのべき乗が含まれ、ベクトルには多項式の係数が含まれる。

${\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}$

行列の次元は、pの場合はd × k _m、qの場合はd × k _nです。無限大を表す行は、最後の列の 1 を除いて常にすべてゼロです。

多項式を掛け合わせるのとは異なり、${\displaystyle p(\cdot )}$そして${\displaystyle q(\cdot )}$評価された値を乗算する${\displaystyle p(a)}$そして${\displaystyle q(a)}$これは単に整数の乗算を行うだけで、元の問題のより小さな例です。評価された各点のペアを乗算するために、乗算手順を再帰的に呼び出します。実際の実装では、オペランドが小さくなるにつれて、アルゴリズムは教科書的な乗算に切り替わります。r を積多項式とすると、この例では次のようになります。

${\displaystyle {\begin{array}{l c l c l c r}r(0)&=&p(0)\,q(0)&=&56789012\times 54321098&=&3084841486175176\\r(1)&=&p(1)\,q(1)&=&135813702\times 97639739&=&13260814415903778\\r(-1)&=&p(-1)\,q(-1)&=&-21988766\times 11199987&=&-246273893346042\\r(-2)&=&p(-2)\,q(-2)&=&-100519632\times -31723594&=&3188843994597408\\r(\infty )&=&p(\infty )\,q(\infty )&=&123456\times 98765&=&12193131840.\end{array}}}$

図に示すように、これらは負の値になることもあります。十分に大きな数の場合、これは最もコストのかかるステップであり、サイズに対して線形ではない唯一のステップです。${\displaystyle m}$そして${\displaystyle n}$。

これは最も複雑なステップであり、評価ステップの逆です。${\displaystyle d}$積多項式上の点${\displaystyle r(\cdot )}$そこで、その係数を決定する必要があります。言い換えれば、右辺のベクトルについて、この行列方程式を解きたいのです。

${\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}$

この行列は評価ステップの行列と同じ方法で構築されますが、${\displaystyle d\times d}$この方程式はガウス消去法のような手法で解くこともできますが、計算コストが高すぎます。そこで、評価点を適切に選択すればこの行列は可逆であるという事実を利用します（ヴァンデルモンド行列も参照）。したがって、次のようになります。

${\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}$

残るは、この行列とベクトルの積を計算することだけです。行列には分数が含まれていますが、結果として得られる係数は整数になるため、加算、減算、および小さな定数による乗算/除算といった整数演算だけで全て実行できます。Toom–Cook における難しい設計上の課題は、この積を計算するための効率的な操作シーケンスを見つけることです。Bodrato ^{[ 6 ]}がToom-3 用に提示したシーケンスの 1 つは次のとおりで、ここでは実行例に対して実行されます。

${\displaystyle {\begin{array}{l c l c r}r_{0}&\leftarrow &r(0)&=&3084841486175176\\r_{4}&\leftarrow &r(\infty )&=&12193131840\\r_{3}&\leftarrow &(r(-2)-r(1))/3&=&(3188843994597408-13260814415903778)/3\\&&&=&-3357323473768790\\r_{1}&\leftarrow &(r(1)-r(-1))/2&=&(13260814415903778-(-246273893346042))/2\\&&&=&6753544154624910\\r_{2}&\leftarrow &r(-1)-r(0)&=&-246273893346042-3084841486175176\\&&&=&-3331115379521218\\r_{3}&\leftarrow &(r_{2}-r_{3})/2+2r(\infty )&=&(-3331115379521218-(-3357323473768790))/2+2\times 12193131840\\&&&=&13128433387466\\r_{2}&\leftarrow &r_{2}+r_{1}-r_{4}&=&-3331115379521218+6753544154624910-12193131840\\&&&=&3422416581971852\\r_{1}&\leftarrow &r_{1}-r_{3}&=&6753544154624910-13128433387466\\&&&=&6740415721237444\end{array}}}$

これで積多項式がわかった${\displaystyle r}$:

${\displaystyle {\begin{array}{rrrl}r(x)=&&3084841486175176&\\&+&6740415721237444&\!\!\!\!x\\&+&3422416581971852&\!\!\!\!x^{2}\\&+&13128433387466&\!\!\!\!x^{3}\\&+&12193131840&\!\!\!\!x^{4}\end{array}}}$

もし私たちが別のものを使っていたら${\displaystyle k_{m},k_{n}}$または評価点によって行列が変わるため、補間戦略も変わりますが、入力に依存しないため、任意のパラメータセットに対してハードコーディングできます。

最後に、r(B) を評価して最終的な答えを得ます。B はbのべき乗なので、B のべき乗による乗算はすべてbの整数桁のシフトになります。実行例では、b = 10 ⁴、B = b ² = 10 ^{8 です}。

これは実際には1234567890123456789012と987654321987654321098の積です。

定義を形式的に適用すると、Toom-1 ( k _m = k _n = 1 ) を考えることができます。これは乗算アルゴリズムではなく、各入力インスタンスを同じインスタンスの再帰呼び出しに自明に還元するため、決して停止しない再帰アルゴリズムになります。このアルゴリズムは 1 つの評価点を必要としますが、その値は定数多項式の「評価」にのみ使用されるため、重要ではありません。したがって、補間行列は単位行列になります。

${\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}$

Toom-1.5 ( k _m = 2、k _n = 1) は依然として退化しています。これは、一方の入力のサイズを半分にすることで再帰的に縮小しますが、もう一方の入力は変更しません。したがって、1 × n乗算アルゴリズムを基本ケースとして提供した場合にのみ、乗算アルゴリズムにすることができます (真の Toom–Cook アルゴリズムは、定数サイズの基本ケースに帰着します)。評価点として 2 つが必要で、ここでは 0 と ∞ を選択します。その補間行列は単位行列になります。

${\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}$

このアルゴリズムは、本質的には長乗算の一種に相当します。つまり、一方の因数の2つの係数を、もう一方の因数の唯一の係数で乗算します。

Toom-2 ( k _m = 2、k _n = 2) は 3 つの評価点を必要とし、ここでは 0、1、および ∞ が選択されます。これは、補間行列が次のようになるカラツバ乗算と同じです。

${\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}$

Toom-2.5 ( k _m = 3、k _n = 2) は 4 つの評価点を必要とし、ここでは 0、1、-1、および ∞ が選択されます。その場合、補間行列は次のようになります。

${\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}$