1.3.1 Karatsuba法

Karatsuba (ソ連, 1962年)

$$X=x_1 b+x_0,\quad Y=y_1 b+y_0$$

とするとき

$$XY =(x_1 b+x_0)(y_1 b+y_0)$$

$$=x_1y_1b^2+(x_1y_0+x_0y_1)b+x_0y_0$$

$$=x_1y_1b^2+\left[x_1y_1+x_0y_0-(x_1-x_0)(y_1-y_0)\right]b+x_0y_0$$

であるから、

$$s_0:=x_0y_0,$$

$$s_2:=x_1y_1,$$

$$XY:=s_2b^2+\left[s_2+s_0-(x_1-x_0)(y_1-y_0)\right]b+s_0$$

と計算すると、乗算３回で $XY$ が計算できる ($b$ の羃をかけるのは桁ずらしで済むことに注意)。

4回の積と２回の和が、３回の積と3回の和と3回の差になった。 再帰的に繰り返すと、極限では、 乗算の計算量は $O(n^{\log_2 3})$ ( $\log_2 3=1.58496\cdots$ ) となる。

資料によっては

$$XY=x_1y_1b^2+\left[(x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0\right]b+x_0y_0$$

に基いた説明をしている。あれれ。