出典: フリー百科事典『ウィキペディア(Wikipedia)』
カラツバ法(カラツバほう)とは、主に多倍長乗算の乗算アルゴリズム(英語版)において、乗算の回数を4分の3にするアルゴリズムである。
加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。
発見者のAnatolii Alexeevitch Karatsuba(Карацуба Анатолий Алексеевич)の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。
従来の乗算は
だったが、Karatsuba法の再帰的適用により、
(
≒1.585)まで計算コストが抑えられる。
アルゴリズム[編集]
単純な例として、被乗数
と乗数
の積
を求める(
)。
まず、被乗数
と乗数
をそれぞれ上位・下位の2つに分割する。
分割の基数を
(例えば3桁ずつに分割するなら
)とすると、



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



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

計算例[編集]
、
、
とすると、




関連項目[編集]