カラツバ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

アルゴリズム[編集]

単純な例として、被乗数Xと乗数Yの積Zを求める(Z = X \times Y)。 まず、被乗数Xと乗数Yをそれぞれ上位・下位の2つに分割する。 分割の基数をb(例えば3桁ずつに分割するなら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_1:=32, x_0:=463)Y=38,030 (y_1:=38, y_0:= 30)b=1000 とすると、

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

関連項目[編集]