カラツバ法

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

従来の乗算の計算量は だったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。

アルゴリズム 単純な例として、数と数の積を求める ()。

まず、数と数をそれぞれ上位・下位の2つに分割する。 分割の基数を （例えば3桁ずつに分割するなら ）とすると、

これら を求めるための乗算を Karatsuba以前の方法 (Long multiplication) で行うと、乗算を4回行うことになる。

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

計算例

とすると、

関連項目 - 1963年。カラツバ法はToom-2の特別な場合である。 ショーンハーゲ・ストラッセン法 - 1971年。高速フーリエ変換/離散フーリエ変換を使うアルゴリズムで、カラツバ法やToom-3より高速である。 - 2007年。上のショーンハーゲ・ストラッセン法より高速である。