Data Structures Algorithms 简明教程
Karatsuba Algorithm
Karatsuba algorithm 由系统用于对两个 n 位数字执行快速乘法，即系统编译器计算乘积所花的时间少于普通乘法的时间。
通常的乘法方法需要 n2 次计算才能得到最终乘积，这是因为在两个数字中的所有数字组合之间都必须执行乘法，然后将子乘积相加以得到最终乘积。此乘法方法称为 Naive Multiplication 。
为了更好地理解此乘法，让我们考虑两个 4 位整数： 1456 和 6533 ，并使用朴素方法找出乘积。
因此， 1456 × 6533 =?
在此朴素乘法方法中，由于这两个数字的位数均为 4，需要执行 16 个个位数 × 个位数乘法。因此，此方法的时间复杂度为 O(42)，因为计算最终结果需要 42 个步骤。
但当 n 的值不断增加时，问题的复杂度也会持续增加。因此，采用 Karatsuba 算法以进行更快的乘法运算。
Karatsuba Algorithm
Karatsuba 算法的主要思想是将多个子问题的乘法运算简化为三个子问题的乘法运算。加法和减法等算术运算用于其他计算。
对于此算法，将两个 n 位数作为输入，并获得这两个数的乘积作为输出。
Step 1 − 在此算法中，我们假设 n 是 2 的幂。
Step 2 − 如果 n = 1，则我们使用乘法表找出 P = XY。
Step 3 − 如果 n > 1，则将 n 位数对半分割，并使用以下公式表示数字 −
X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2其中，X1、X2、Y1、Y2 各有 n/2 位。
Step 4 − 取变量 Z = W – (U + V)，
其中，
U = X1Y1, V = X2Y2
W = (X1 + X2) (Y1 + Y2), Z = X1Y2 + X2Y1.Step 5 − 然后，在公式中替换值后获得乘积 P −
P = 10n(U) + 10n/2(Z) + V
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2.Step 6 − 通过分别传递子问题 (X1, Y1)、(X2, Y2) 和 (X1 + X2, Y1 + Y2)，递归调用算法。分别将返回值存储在变量 U、V 和 W 中。
Example
让我们使用 Karatsuba 方法解决上面提出的同一问题，1456 × 6533 −
Karatsuba 方法采用分治法，将问题划分为多个子问题，并应用递归来简化乘法运算。
Step 1
假设 n 是 2 的幂，以以下形式重写 n 位数 −
X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2我们得到，
1456 = 102(14) + 56
6533 = 102(65) + 33首先让我们尝试简化数学表达式，我们得到，
(1400 × 6500) + (56 × 33) + (1400 × 33) + (6500 × 56) =
104 (14 × 65) + 102 [(14 × 33) + (56 × 65)] + (33 × 56)因为相乘两个两位数比相乘两个四位数更容易求解，故上面的表达式是给定乘法问题的简化版本。
然而，这对于人脑而言是正确的，但是对于系统编译器而言，上面的表达式仍然具有与普通朴素乘法相同的时间复杂度。因为它具有 4 个两位数 × 两位数乘法，所以所需时间复杂度为 −
14 × 65 → O(4)
14 × 33 → O(4)
65 × 56 → O(4)
56 × 33 → O(4)
= O (16)因此，需要进一步简化计算。
Step 2
X = 1456
Y = 6533因为 n 不等于 1，该算法跳到步骤 3。
X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2我们得到，
1456 = 102(14) + 56
6533 = 102(65) + 33计算 Z = W – (U + V) −
Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2)
Z = X1Y2 + X2Y1
Z = (14 × 33) + (65 × 56)最终结果，
P = 10n. U + 10n/2. Z + V
= 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2
= 104 (14 × 65) + 102 [(14 × 33) + (65 × 56)] + (56 × 33)子问题可进一步分解为更小的子问题；因此，该算法再次递归调用。
Step 3
X1 和 Y1 作为参数 X 和 Y 进行传递。
所以现在 X = 14，Y = 65
X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
14 = 10(1) + 4
65 = 10(6) + 5计算 Z = W – (U + V) −
Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2)
Z = X1Y2 + X2Y1
Z = (1 × 5) + (6 × 4) = 29
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2
= 102 (1 × 6) + 101 (29) + (4 × 5)
= 910Step 4
X2 和 Y2 作为参数 X 和 Y 进行传递。
所以现在 X = 56，Y = 33
X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
56 = 10(5) + 6
33 = 10(3) + 3计算 Z = W – (U + V) −
Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2)
Z = X1Y2 + X2Y1
Z = (5 × 3) + (6 × 3) = 33
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2
= 102 (5 × 3) + 101 (33) + (6 × 3)
= 1848Step 5
X1 + X2 和 Y1 + Y2 作为参数 X 和 Y 进行传递。
所以现在 X = 70，Y = 98
X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
70 = 10(7) + 0
98 = 10(9) + 8计算 Z = W – (U + V) −
Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2)
Z = X1Y2 + X2Y1
Z = (7 × 8) + (0 × 9) = 56
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2
= 102 (7 × 9) + 101 (56) + (0 × 8)
=Step 6
最终结果，
P = 10n. U + 10n/2. Z + VU = 910
V = 1848
Z = W – (U + V) = 6860 – (1848 + 910) = 4102将相应的值代入公式中，
P = 10n. U + 10n/2. Z + V
P = 104 (910) + 102 (4102) + 1848
P = 91,00,000 + 4,10,200 + 1848
P = 95,12,048Analysis
卡拉楚巴算法是一种递归算法；因为它在执行期间调用自己的较小实例。
根据该算法，它只对 n/2 位数字调用自己三次即可求得两个 n 位数字的最终乘积。
现在，如果 T(n) 表示执行乘法时所需的数字乘法次数，
T(n) = 3T(n/2)
此方程是一个简单的递推关系，可解为：
Apply T(n/2) = 3T(n/4) in the above equation, we get:
T(n) = 9T(n/4)
T(n) = 27T(n/8)
T(n) = 81T(n/16)
.
.
.
.
T(n) = 3i T(n/2i) is the general form of the recurrence relation
of Karatsuba algorithm.递推关系可使用 master’s theorem 求解，因为我们有一个除法函数，形式为：
T(n) = aT(n/b) + f(n), where, a = 3, b = 2 and f(n) = 0
which leads to k = 0.由于 f(n) 代表递归外部完成的工作，即卡拉楚巴中的加法和减法算术运算，这些算术运算不属于时间复杂度。
检查“a”和“bk”之间的关系。
a > bk = 3 > 20根据大师定理，应用情况 1。
T(n) = O(nlogb a)
T(n) = O(nlog 3)卡拉苏巴算法快速乘法的的时间复杂度为 O(nlog 3) 。