カラツバ法

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

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

アルゴリズム 
単純な例として、被乗数と乗数の積を求める()。
まず、被乗数と乗数をそれぞれ上位・下位の2つに分割する。
分割の基数を（例えば3桁ずつに分割するなら）とすると、

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

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

計算例 
 、
 、 とすると、

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

アルゴリズム
数学に関する記事
数学のエポニム