Karatsuba法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
Karatsuba法（カラツバほう）とは、主に多倍長乗算において、乗算の使用回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遙かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。
従来の乗算はO(n2)だったが、Karatsuba法の再帰的適用により、
（log23≒1.585）まで計算コストが抑えられる。
[編集] アルゴリズム
単純な例として、被乗数Xと乗数Yの積Zを求める(
)。 まず、被乗数Xと乗数Yをそれぞれ上位・下位の2つに分割する。 分割の基数をb（例えば3桁ずつに分割するならb: = 1000）とすると、
この乗算をKaratsuba以前の方法で行うと、乗算を4回行うことになる。
Karatsubaの方法では、乗算を3回で済ませられる。
[編集] 計算例
X = 32,463 (x1: = 32,x0: = 463)、 Y = 38,030 (y1: = 38,y0: = 30)、b = 1000 とすると、
- z2: = x1y1 = 1216
- z0: = x0y0 = 13890
- z1: = z2 + z0 − (x1 − x0)(y1 − y0) = 1216 + 13890 − ( − 431)(8) = 18554
- Z = 1216b2 + 18554b + 13890 = 1,216,000,000 + 18,554,000 + 13,890 = 1,234,567,890
