[算法系列之九]Karatsuba快速相乘算法

karatsuba乘法是一種快速乘法。此算法在1960年由anatolii alexeevitch karatsuba 提出，并于1962年得以發表。

此算法主要用于兩個大數相乘。普通乘法的複雜度是n2，而karatsuba算法的複雜度僅為3nlog3≈3n1.585（log3是以2為底的）

karatsuba算法主要應用于兩個大數的相乘，原理是将大數分成兩段後變成較小的數位，然後做3次乘法，并附帶少量的加法操作和移位操作。

現有兩個大數，x，y。

首先将x，y分别拆開成為兩部分，可得x1，x0，y1，y0。他們的關系如下：

x = x1 * 10m + x0；

y = y1 * 10m + y0。其中m為正整數，m < n，且x0，y0 小于 10m。

那麼 

xy    = (x1 * 10m + x0)(y1 * 10m

+ y0)

        =z2 * 102m

+ z1 * 10m + z0，其中：

z2 = x1 * y1；

z1 = x1 * y0 + x0 * y1；

z0 = x0 * y0。

此步驟共需4次乘法，但是由karatsuba改進以後僅需要3次乘法。因為：

z1 = x1 * y0+ x0 * y1

z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，

故x0 * y0 便可以由加減法得到。

是以：

  x*y = z2 *  102m +  z1 *  10m

+   z0

z2 = x1 * y1

z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0 =  (x1 + x0) * (y1 + y0) - x1 * y1 - z0

z0 = x0 * y0

recursively computer  (x1*y1)

recursively computer  (x1 + x0) * (y1 + y0)

recursively computer  (x0 * y0)

設x = 12345，y=6789，令m=3。那麼有：

12345 = 12 * 1000 + 345；

6789 = 6 * 1000 + 789。

下面計算：

z2 = 12 * 6 = 72；

z0 = 345 * 789 = 272205；

z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。

然後我們按照移位公式（xy = z2 * 102m  + z1 * 10m  +

z0）可得：

xy = 72 * 10002 + 11538 * 1000 + 272205 = 83810205。