カラツバ法

カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者の（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。従来の乗算は<math>O(n^2)</math>だったが、Karatsuba法の再帰的適用により、<math>O(n^)</math>（<math>\\log_23</math>≒1.585）まで計算コストが抑えられる。