円周率.jp (http://xn--w6q13e505b.jp/method/karatsuba.html)

Karatsuba 法

ここでは基数を $R$ とする形で定義されている, 長さが $2n$ の 2 つの多倍長数

\[ 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 \]

の積 $AB$ を計算したいとしよう. このとき,通常の筆算と同じ様に計算を行うと $O(n^2)$ の演算が必要になる.

次に各値を以下のように 2 つに分解し,右辺のように認識しなおそう. $R^n$ に関わる括弧を外せば元と同じ式になることは簡単に確認できる.

\[ 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 \]

この形式のまま通常の筆算と同様の計算を行うと, $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 回ずつ現れていることに注意してほしい.

\[ T = A_1 + A_0,\ U = B_1 + B_0 \] \[ AB = A_1B_1 R^{2n} + (TU - A_1B_1 - A_0B_0) R^n + A_0B_0 \]

この変形を再帰的に適用することで, $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} \] \[ \therefore \begin{cases} M(n)= n^{\log_23}\\A(n)=8(n^{\log_23}-n) \end{cases} \]

となる. $8n$ の部分の内わけは $T$,$U$ を求めるために $n$ 回ずつ,括弧内を求めるために $2n$ 回の加算を 2 回,最後に上下の結果と合わせる際に必要な加算が 上下 $n$ 回ずつ,となっている.

以上のことから,Karatsuba 法の計算量は $O(n^{\log_23}) \sim O(n^{1.585})$ となり, 単純な筆算方式より効率的なことが示された.