カラツバ法

Summarize Timeline Top Qs Fact Check

単純な例として、数${\displaystyle X}$と数${\displaystyle Y}$の積${\displaystyle Z}$を求める (${\displaystyle Z=X\times Y}$)。

まず、数${\displaystyle X}$と数${\displaystyle Y}$をそれぞれ上位・下位の2つに分割する。 分割の基数を ${\displaystyle b}$（例えば3桁ずつに分割するなら ${\displaystyle b:=1000}$）とすると、

${\displaystyle {\begin{aligned}X&:=x_{1}\times b+x_{0}\\Y&:=y_{1}\times b+y_{0}\\Z&:=z_{2}\times b^{2}+z_{1}\times b+z_{0}\end{aligned}}}$

これら z₀, z₁, z₂ を求めるための乗算を Karatsuba以前の方法 (Long multiplication) で行うと、乗算を4回行うことになる。

${\displaystyle {\begin{aligned}z_{2}&:=x_{1}\times y_{1}\\z_{1}&:=x_{1}\times y_{0}+x_{0}\times y_{1}\\z_{0}&:=x_{0}\times y_{0}\end{aligned}}}$

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

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

Summarize Timeline Top Qs Fact Check

${\displaystyle {\begin{aligned}X&=32{,}463&(x_{1}&:=32,\;x_{0}:=463)\\Y&=38{,}030&(y_{1}&:=38,\;y_{0}:={\phantom {0}}30)\\b&={\phantom {0}}1{,}000\end{aligned}}}$

とすると、

${\displaystyle {\begin{aligned}z_{2}&:=x_{1}y_{1}=1216\\z_{0}&:=x_{0}y_{0}=13890\\z_{1}&:=z_{2}+z_{0}-(x_{1}-x_{0})(y_{1}-y_{0})=1216+13890-(-431)(8)=18554\\Z&=1216\,b^{2}+18554\,b+13890=1{,}216{,}000{,}000+18{,}554{,}000+13{,}890=1{,}234{,}567{,}890\end{aligned}}}$

• トム・クック乗算（英語版） - 1963年。カラツバ法はToom-2の特別な場合である。
• ショーンハーゲ・ストラッセン法 - 1971年。高速フーリエ変換/離散フーリエ変換を使うアルゴリズムで、カラツバ法やToom-3より高速である。
• フューラーのアルゴリズム（ロシア語版） - 2007年。上のショーンハーゲ・ストラッセン法より高速である。