コンテンツにスキップ

カラツバ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

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

アルゴリズム

[編集]

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

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

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

計算例

[編集]

とすると、

関連項目

[編集]