プログラミング/多倍長整数/Toom-Cook乗算

中学校数学の範囲で理解できるように、Toom-Cook乗算（Toom-3）について簡単に解説します。

Toom-Cook乗算（Toom-3）は、大きな数同士の掛け算を効率的に計算するためのアルゴリズムです。カラツバ法をさらに発展させたもので、より大きな数の掛け算に対して効果的です。通常の掛け算やカラツバ法と比べて、Toom-3は数をより細かく分割し、より多くの評価点を使用することで、さらに計算量を減らすことができます。

通常の掛け算とカラツバ法

通常の掛け算では、 $n$ 桁の数同士を掛けると、 $n^{2}$ 回の掛け算が必要です。カラツバ法では、2つに分割して3回の掛け算で計算します。

Toom-3の考え方

Toom-3は、数を3つに分割し、5つの評価点を使用します。具体的には、以下のように計算します：

掛け算する2つの数をそれぞれ3つの部分に分割する
5つの評価点（通常は0, 1, -1, 2, ∞）で多項式を評価する
評価点での値を掛け合わせる
結果を補間して元の多項式の係数を求める
最終的な結果を計算する

Toom-3の具体例

例えば、3桁の数 $x$ と $y$ を掛けるとします。これらを次のように表現できます：

$x=a_{2}\times 10^{2}+a_{1}\times 10+a_{0}$
$y=b_{2}\times 10^{2}+b_{1}\times 10+b_{0}$

これを多項式として表すと：

$x=a_{2}r^{2}+a_{1}r+a_{0}$
$y=b_{2}r^{2}+b_{1}r+b_{0}$

ここで $r=10$ です。 Toom-3では、この多項式を5つの点（例：0, 1, -1, 2, 3）で評価し、それぞれの点での値を掛け合わせます。その後、結果を補間して元の多項式の係数を求めます。

なぜ効率的か

Toom-3は、カラツバ法よりもさらに大きな数の掛け算に対して効率的です。理論的には、 $n$ 桁の数同士の掛け算を $O(n^{\log _{3}5})$ の計算量で行うことができます。これは通常の掛け算（ $O(n^{2})$ ）やカラツバ法（ $O(n^{\log _{2}3})$ ）よりも効率的です。

まとめ

Toom-Cook乗算（Toom-3）は、数を3つに分割し、5つの評価点を使用することで、大きな数の掛け算をより効率的に行うアルゴリズムです。カラツバ法をさらに発展させたもので、特に非常に大きな数の掛け算において効果を発揮します。