円周率.jp > 多数桁計算 > Karatsuba 法

Karatsuba 法

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

Aa2n-1 R2n-1a2n-2 R2n-2+…+ a0
Bb2n-1 R2n-1b2n-2 R2n-2+…+ b0

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

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

A = (a2n-1 Rn-1+…+ anRn +(an-1 Rn-1+…+ a0) = A1RnA0
B = (b2n-1 Rn-1+…+ bnRn +(bn-1 Rn-1+…+ b0) = B1RnB0

この形式のまま通常の筆算と同様の計算を行うと, n 桁同士の乗算を 4 回行う必要がある事が分かる.

ABA1B1 R2n + (A0B1A1B0RnA0B0

これに対し Karatsuba 法では次のように計算を行うことで n 桁同士の乗算の回数を 3 回に抑えている. パッと見ただけでは乗算回数が増えているように見えるが, A1B1A0B0 が 2 回ずつ現れていることに注意してほしい.

TA1A0UB1B0ABA1B1 R2n + (TUA1B1A0B0RnA0B0

この変形を再帰的に適用することで, n 桁での乗算に必要な要素レベルの乗算回数が Mn) 回,加算回数が An) 回であるとするとき,

M(2n 3Mn), M(1) = 1   ∴ Mn) = nlog23
A(2n 3An) + 8n A(1) = 0   ∴ An) = 8(nlog23n)

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

以上のことから,Karatsuba 法の計算量は O(3log2n) = O(nlog23) ≒ O(n1.585) となり, 単純な筆算方式より効率的なことが示された.