「カラツバ法」の版間の差分
2023年3月26日 (日) 07:15時点における最新版
カラツバ法(カラツバほう)とは、主に多倍長乗算の乗算アルゴリズム (英語版)において、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba(Карацуба Анатолий Алексеевич)の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。
従来の乗算は{\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}
関連項目
[編集 ]- カラツバ法(1960年)
- en:Toom–Cook multiplication(1963年。カラツバ法はToom-2の特別な場合である)
- ショーンハーゲ・ストラッセン法(1971年。高速フーリエ変換/離散フーリエ変換を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである)
- en:Fürer's algorithm(2007年。Schönhage–Strassenより高速)