カラツバ法のソースを表示

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

従来の乗算は<math>O(n^2)</math>だったが、Karatsuba法の再帰的適用により、<math>O(n^{\log_23})</math>（<math>\log_23</math>≒1.585）まで計算コストが抑えられる。

== アルゴリズム ==
単純な例として、被乗数<math>X</math>と乗数<math>Y</math>の積<math>Z</math>を求める(<math>Z = X \times Y</math>)。
まず、被乗数<math>X</math>と乗数<math>Y</math>をそれぞれ上位・下位の2つに分割する。
分割の基数を<math>b</math>（例えば3桁ずつに分割するなら<math>b:=1000</math>）とすると、
:<math>X := x_1 \cdot b + x_0</math>
:<math>Y := y_1 \cdot b + y_0</math>
:<math>Z := z_2 \cdot b^2 + z_1 \cdot b + z_0</math>

この乗算をKaratsuba以前の方法（[[:en:Multiplication algorithm#Long multiplication|Long multiplication]]）で行うと、乗算を4回行うことになる。
:<math>z_2 := x_1 \times y_1</math>
:<math>z_0 := x_0 \times y_0</math>
:<math>z_1 := x_1 \times y_0 + x_0 \times y_1</math>

Karatsubaの方法では、乗算を3回で済ませられる。
:<math>z_1 := z_2 + z_0 - (x_1 - x_0) \times (y_1 - y_0)</math>

== 計算例 ==
<math>X=32,463</math> <math>(x_1:=32, x_0:=463)</math>、
<math>Y=38,030</math> <math>(y_1:=38, y_0:= 30)</math>、<math>b=1000</math> とすると、
:<math>z_2:=x_1 y_1=1216</math>
:<math>z_0:=x_0 y_0=13890</math>
:<math>z_1:=z_2+z_0-(x_1-x_0)(y_1-y_0)=1216+13890-(-431)(8)=18554</math>
:<math>Z=1216 b^2 + 18554 b + 13890 = 1,216,000,000 + 18,554,000 + 13,890 = 1,234,567,890</math>

== 関連項目 ==
* カラツバ法（1960年）
* [[:en:Toom–Cook multiplication]]（1963年。カラツバ法はToom-2の特別な場合である）
* [[ショーンハーゲ・ストラッセン法]]（1971年。[[高速フーリエ変換]]/[[離散フーリエ変換]]を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである）
* [[:en:Fürer's algorithm]]（2007年。Schönhage–Strassenより高速）

{{DEFAULTSORT:からつはほう}}
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]