Karatsuba 法
前提条件として、基数 $R$ で定義される長さ $2n$ の多倍長整数
\[ \begin{eqnarray} A &=& a_{2n-1}R^{2n-1} + a_{2n-2}R^{2n-2} + \cdots + a_0\\ B &=& b_{2n-1}R^{2n-1} + b_{2n-2}R^{2n-2} + \cdots + b_0 \end{eqnarray} \]の積 $AB$ を計算したいとしよう。 現実的には同じ長さということは難しいので、一部の上位桁を 0 と設定することで以下の議論を進める。 このとき通常の筆算と同じ様に計算を行うと $O(n^2)$ の演算が必要になる。
次に各値を以下のように半分の長さの多倍長整数 2 つずつに分解し、 右辺のように認識しなおそう。
\[ \begin{eqnarray} A &=& (a_{2n-1}R^{n-1} + \cdots + a_n) R^n + (a_{n-1}R^{n-1} + \cdots + a_0) &=& A_1R^n + A_0\\ B &=& (b_{2n-1}R^{n-1} + \cdots + b_n) R^n + (b_{n-1}R^{n-1} + \cdots + b_0) &=& B_1R^n + B_0 \end{eqnarray} \]この形式のまま通常の筆算と同様の計算を行うと、 $n$ 桁同士の乗算を 4 回行う必要がある事が分かる。
\[ AB = A_1B_1 R^{2n} + (A_0B_1 + A_1B_0)R^n + A_0B_0 \]これに対し Karatsuba 法では次のように計算を行うことで $n$ 桁同士の乗算の回数を 3 回に抑えている。 パッと見ただけでは乗算回数が増えているように見えるが、 $A_1B_1$、$A_0B_0$ が 2 回ずつ現れているので再利用できることに注意してほしい。
\[ AB = A_1B_1 R^{2n}+((A_1+A_0)(B_1+B_0)-A_1B_1-A_0B_0)R^n+A_0B_0 \]加減算の回数は増えているものの、長さ $n$ 同士の乗算回数を 4 回から 3 回に減らすことができた。 この変形は再帰的に適用できるので、適用する度に計算量を抑えることができる。
計算量
ということで計算量を見積もってみよう。 $n$ 桁同士の乗算に必要な要素レベルの乗算回数を $M(n)$ 回、加算回数を $A(n)$ 回とするとき、 以下のような漸化式が成り立つ。
\[ \begin{cases} M(2n)= 3M(n)\\ A(2n) = 3A(n) + 8n \end{cases},\ \begin{cases} M(1)= 1\\ A(1) = 0 \end{cases} \]$8n$ の部分の内わけは $A_1+A_0$、$B_1+B_0$ の計算に $n$ 回ずつ、括弧内を求めるために $2n$ 回の加減算を 2 回、 最後に上下の結果と合わせる際に必要な加減算がそれぞれ $n$ 回ずつ、となっている。 これを解くと
\[ \therefore \begin{cases} M(n)= n^{\log_23}\\A(n)=8(n^{\log_23}-n) \end{cases} \]となることから、Karatsuba 法の計算量は $O(n^{\log_23}) \simeq O(n^{1.585})$ となることが分かった。
筆算で同様の見積もりをしてみると
\[ \begin{cases} M(n)= n^2\\A(n)=2n(n-1) \end{cases} \]となる(概算)のでこれらをそのまま比較すると $n \gt 8.46$ で Karatsuba 法の方が効率的に計算できるということになる。 しかし実際にはプログラムの実装次第でこの閾値は多少前後するので 目安の数値として考えてもらいたい。