カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者の（）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。従来の乗算はformula_1だったが、Karatsuba法の再帰的適用により、formula_2（formula_3≒1.585）まで計算コストが抑えられる。単純な例として、被乗数formula_4と乗数formula_5の積formula_6を求める(formula_7)。まず、被乗数formula_4と乗数formula_5をそれぞれ上位・下位の2つに分割する。分割の基数をformula_10（例えば3桁ずつに分割するならformula_11）とすると、この乗算をKaratsuba以前の方法（）で行うと、乗算を4回行うことになる。Karatsubaの方法では、乗算を3回で済ませられる。formula_19 formula_20、formula_21 formula_22、formula_23 とすると、

出典:wikipedia