カラツバ法

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

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

アルゴリズム[編集]

単純な例として、被乗数 $X$ $X$ と乗数 $Y$ $Y$ の積 $Z$ $Z$ を求める( $Z=X\times Y$ $Z=X\times Y$ )。まず、被乗数 $X$ $X$ と乗数 $Y$ $Y$ をそれぞれ上位・下位の2つに分割する。分割の基数を $b$ $b$ （例えば3桁ずつに分割するなら $b:=1000$ $b:=1000$ ）とすると、

X:=x_{1}\cdot b+x_{0}

Y:=y_{1}\cdot b+y_{0}

Z:=z_{2}\cdot b^{2}+z_{1}\cdot b+z_{0}

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

z_{2}:=x_{1}\times y_{1}

z_{0}:=x_{0}\times y_{0}

z_{1}:=x_{1}\times y_{0}+x_{0}\times y_{1}

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

z_{1}:=z_{2}+z_{0}-(x_{1}-x_{0})\times (y_{1}-y_{0})

計算例[編集]

$X=32,463$ $X=32,463$ $(x_{1}:=32,x_{0}:=463)$ $(x_{1}:=32,x_{0}:=463)$ 、 $Y=38,030$ $Y=38,030$ $(y_{1}:=38,y_{0}:=30)$ $(y_{1}:=38,y_{0}:=30)$ 、 $b=1000$ $b=1000$ とすると、