1.3 整数乘法Karatsuba算法

  Karatsuba算法与复数乘法类似，都是通过巧妙的方式，将乘法次数由4次减少到3次。Karatsuba算法是将两个整数按高低位进行拆分。假设有以下两个数x和y，x的高位是$x_1$，低位是$x_0$，y的高位是$y_1$，低位是$y_0$，假设进制为二进制。
  假设低位的位数为m，那么传统乘法的计算方式是$xy=x_1{y}_1{2}^{2m}+(x_1{y}_0+x_0{y}_1)2^m+x_0{y}_0$。这种方式用了4次乘法。
  Karatsuba算法采用三个变量，将乘法次数减少到三次，算法如下：
$$\begin{gathered} p_0=x_0{y}_0 \\ {p}_1=x_1{y}_1 \\ {p}_2=(x_1+x_0)(y_1+y_0)-p_1-p_0 \\ xy=p_1{2}^{2m}+p_2{2}^m+p_0 \end{gathered}$$
  算法比较简单：

# _*_ coding:utf-8 _*_

def mul(x0, x1, y0, y1, base, m):
    p0 = x0 * y0
    p1 = x1 * y1
    p2 = (x1 + x0) * (y1 + y0) - p1 - p0
    p = base ** m

    return p1 * p * p + p * p2 + p0


if __name__ == '__main__':
    # 1234 * 1432
    print(mul(34, 12, 32, 14, 10, 2))