カラツバ法

カラツバ法（カラツバほう）とは、主に多倍長乗算のテンプレート:仮リンクにおいて、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba（テンプレート:Lang）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。

従来の乗算は$O(n^2)$だったが、Karatsuba法の再帰的適用により、$O(n^{{\log }_{2}3})$（${\log }_{2}3$≒1.585）まで計算コストが抑えられる。

アルゴリズム

単純な例として、被乗数$X$と乗数$Y$の積$Z$を求める($Z=X\times Y$)。 まず、被乗数$X$と乗数$Y$をそれぞれ上位・下位の2つに分割する。 分割の基数を$b$（例えば3桁ずつに分割するなら$b:=1000$）とすると、

$X:=x_1\cdot b+x_0$

$Y:=y_1\cdot b+y_0$

$Z:=z_2\cdot b^2+z_1\cdot b+z_0$

この乗算をKaratsuba以前の方法（Long multiplication）で行うと、乗算を4回行うことになる。

$z_2:=x_1\times y_1$

$z_0:=x_0\times y_0$

$z_1:=x_1\times y_0+x_0\times y_1$

Karatsubaの方法では、乗算を3回で済ませられる。

$z_1:=z_2+z_0-(x_1-x_0)\times (y_1-y_0)$

計算例

$X=32,463$ $(x_1:=32,x_0:=463)$、 $Y=38,030$ $(y_1:=38,y_0:=30)$、$b=1000$ とすると、

$z_2:=x_1{y}_1=1216$

$z_0:=x_0{y}_0=13890$

$z_1:=z_2+z_0-(x_1-x_0)(y_1-y_0)=1216+13890-(-431)(8)=18554$

$Z=1216b^2+18554b+13890=1,216,000,000+18,554,000+13,890=1,234,567,890$

関連項目

• カラツバ法（1960年）
• en:Toom–Cook multiplication（1963年。カラツバ法はToom-2の特別な場合である）
• ショーンハーゲ・ストラッセン法（1971年。高速フーリエ変換/離散フーリエ変換を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである）
• en:Fürer's algorithm（2007年。Schönhage–Strassenより高速）