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

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

アルゴリズム

編集

単純な例として、被乗数 と乗数 の積 を求める( )。 まず、被乗数 と乗数 をそれぞれ上位・下位の2つに分割する。 分割の基数を (例えば3桁ずつに分割するなら )とすると、

 
 
 

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

 
 
 

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

 

計算例

編集

        とすると、

 
 
 
 

関連項目

編集