カラツバ法
カラツバ法(カラツバほう)とは、主に多倍長乗算の乗算アルゴリズムにおいて、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba(Карацуба Анатолий Алексеевич)の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。
従来の乗算は[math]O(n^2)[/math]だったが、Karatsuba法の再帰的適用により、[math]O(n^{\log_23})[/math]([math]\log_23[/math]≒1.585)まで計算コストが抑えられる。
アルゴリズム
単純な例として、被乗数[math]X[/math]と乗数[math]Y[/math]の積[math]Z[/math]を求める([math]Z = X \times Y[/math])。 まず、被乗数[math]X[/math]と乗数[math]Y[/math]をそれぞれ上位・下位の2つに分割する。 分割の基数を[math]b[/math](例えば3桁ずつに分割するなら[math]b:=1000[/math])とすると、
- [math]X := x_1 \cdot b + x_0[/math]
- [math]Y := y_1 \cdot b + y_0[/math]
- [math]Z := z_2 \cdot b^2 + z_1 \cdot b + z_0[/math]
この乗算をKaratsuba以前の方法(Long multiplication)で行うと、乗算を4回行うことになる。
- [math]z_2 := x_1 \times y_1[/math]
- [math]z_0 := x_0 \times y_0[/math]
- [math]z_1 := x_1 \times y_0 + x_0 \times y_1[/math]
Karatsubaの方法では、乗算を3回で済ませられる。
- [math]z_1 := z_2 + z_0 - (x_1 - x_0) \times (y_1 - y_0)[/math]
計算例
[math]X=32,463[/math] [math](x_1:=32, x_0:=463)[/math]、 [math]Y=38,030[/math] [math](y_1:=38, y_0:= 30)[/math]、[math]b=1000[/math] とすると、
- [math]z_2:=x_1 y_1=1216[/math]
- [math]z_0:=x_0 y_0=13890[/math]
- [math]z_1:=z_2+z_0-(x_1-x_0)(y_1-y_0)=1216+13890-(-431)(8)=18554[/math]
- [math]Z=1216 b^2 + 18554 b + 13890 = 1,216,000,000 + 18,554,000 + 13,890 = 1,234,567,890[/math]
関連項目
- カラツバ法(1960年)
- en:Toom–Cook multiplication(1963年。カラツバ法はToom-3の特別な場合である)
- ショーンハーゲ・ストラッセン法(1971年。高速フーリエ変換/離散フーリエ変換を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである)
- en:Fürer's algorithm(2007年。Schönhage–Strassenより高速)