カラツバ法

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

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

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

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

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

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

 計算例 

とすると、

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

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