カラツバ法(カラツバほう)とは、主に多倍長乗算の乗算アルゴリズム(英語版)において、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba(Карацуба Анатолий Алексеевич)の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。
従来の乗算は
だったが、Karatsuba法の再帰的適用により、
(
≒1.585)まで計算コストが抑えられる。
アルゴリズム
単純な例として、被乗数
と乗数
の積
を求める(
)。 まず、被乗数
と乗数
をそれぞれ上位・下位の2つに分割する。 分割の基数を
(例えば3桁ずつに分割するなら
)とすると、
![{\displaystyle X:=x_{1}\cdot b+x_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/500aa01587fb0eddff830322894f4358a4765e05)
![{\displaystyle Y:=y_{1}\cdot b+y_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/533cba6cd3014418701cd18ea9eeda2f6559ee71)
![{\displaystyle Z:=z_{2}\cdot b^{2}+z_{1}\cdot b+z_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2863408425f5054375a615f108af4e52f53f7afc)
この乗算をKaratsuba以前の方法(Long multiplication)で行うと、乗算を4回行うことになる。
![{\displaystyle z_{2}:=x_{1}\times y_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04175f7239f9b5b8b41a15186d7c935cfd122f5d)
![{\displaystyle z_{0}:=x_{0}\times y_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/939e89718816b7a8c91e65beb8c8bcbeba959c6e)
![{\displaystyle z_{1}:=x_{1}\times y_{0}+x_{0}\times y_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ea167c49fac9f508af23097c3aaf2a2b47d654)
Karatsubaの方法では、乗算を3回で済ませられる。
![{\displaystyle z_{1}:=z_{2}+z_{0}-(x_{1}-x_{0})\times (y_{1}-y_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c18f484537192fabb7b4d8aed118fde8ecc8ebe4)
計算例
、
、
とすると、
![{\displaystyle z_{2}:=x_{1}y_{1}=1216}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0f80ed36d5f04bc3accee5d671f2da5d2ab54eb)
![{\displaystyle z_{0}:=x_{0}y_{0}=13890}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9debee7263fa0f35273c7fc451df41db910d4d5)
![{\displaystyle z_{1}:=z_{2}+z_{0}-(x_{1}-x_{0})(y_{1}-y_{0})=1216+13890-(-431)(8)=18554}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fb8d69c40f2d904c5b86a0b60e766a5cb095803)
![{\displaystyle Z=1216b^{2}+18554b+13890=1,216,000,000+18,554,000+13,890=1,234,567,890}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e3236549fad4a139425692f78183beca68b9c5a)
関連項目
- カラツバ法(1960年)
- en:Toom–Cook multiplication(1963年。カラツバ法はToom-2の特別な場合である)
- ショーンハーゲ・ストラッセン法(1971年。高速フーリエ変換/離散フーリエ変換を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである)
- en:Fürer's algorithm(2007年。Schönhage–Strassenより高速)