カラツバ法 カラツバ法の概要

ウィキペディア

カラツバ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/03/26 07:15 UTC 版)

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

アルゴリズム

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

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

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

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

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

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

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

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

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

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

計算例

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

${\displaystyle z_{2}:=x_{1}y_{1}=1216}$

${\displaystyle z_{0}:=x_{0}y_{0}=13890}$

${\displaystyle z_{1}:=z_{2}+z_{0}-(x_{1}-x_{0})(y_{1}-y_{0})=1216+13890-(-431)(8)=18554}$

${\displaystyle Z=1216b^{2}+18554b+13890=1,216,000,000+18,554,000+13,890=1,234,567,890}$