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