Data Structures Algorithms 简明教程

Karatsuba Algorithm

Karatsuba algorithm 由系统用于对两个 n 位数字执行快速乘法，即系统编译器计算乘积所花的时间少于普通乘法的时间。

The Karatsuba algorithm is used by the system to perform fast multiplication on two n-digit numbers, i.e. the system compiler takes lesser time to compute the product than the time-taken by a normal multiplication.

通常的乘法方法需要 n2 次计算才能得到最终乘积，这是因为在两个数字中的所有数字组合之间都必须执行乘法，然后将子乘积相加以得到最终乘积。此乘法方法称为 Naive Multiplication 。

The usual multiplication approach takes n2 computations to achieve the final product, since the multiplication has to be performed between all digit combinations in both the numbers and then the sub-products are added to obtain the final product. This approach of multiplication is known as Naive Multiplication.

为了更好地理解此乘法，让我们考虑两个 4 位整数： 1456 和 6533 ，并使用朴素方法找出乘积。

To understand this multiplication better, let us consider two 4-digit integers: 1456 and 6533, and find the product using Naive approach.

因此， 1456 × 6533 =?

So, 1456 × 6533 =?

在此朴素乘法方法中，由于这两个数字的位数均为 4，需要执行 16 个个位数 × 个位数乘法。因此，此方法的时间复杂度为 O(42)，因为计算最终结果需要 42 个步骤。

In this method of naive multiplication, given the number of digits in both numbers is 4, there are 16 single-digit × single-digit multiplications being performed. Thus, the time complexity of this approach is O(42) since it takes 42 steps to calculate the final product.

但当 n 的值不断增加时，问题的复杂度也会持续增加。因此，采用 Karatsuba 算法以进行更快的乘法运算。

But when the value of n keeps increasing, the time complexity of the problem also keeps increasing. Hence, Karatsuba algorithm is adopted to perform faster multiplications.

Karatsuba Algorithm

Karatsuba 算法的主要思想是将多个子问题的乘法运算简化为三个子问题的乘法运算。加法和减法等算术运算用于其他计算。

The main idea of the Karatsuba Algorithm is to reduce multiplication of multiple sub problems to multiplication of three sub problems. Arithmetic operations like additions and subtractions are performed for other computations.

对于此算法，将两个 n 位数作为输入，并获得这两个数的乘积作为输出。

For this algorithm, two n-digit numbers are taken as the input and the product of the two number is obtained as the output.

Step 1 − 在此算法中，我们假设 n 是 2 的幂。

Step 1 − In this algorithm we assume that n is a power of 2.

Step 2 − 如果 n = 1，则我们使用乘法表找出 P = XY。

Step 2 − If n = 1 then we use multiplication tables to find P = XY.

Step 3 − 如果 n > 1，则将 n 位数对半分割，并使用以下公式表示数字 −

Step 3 − If n > 1, the n-digit numbers are split in half and represent the number using the formulae −

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2

其中，X1、X2、Y1、Y2 各有 n/2 位。

where, X1, X2, Y1, Y2 each have n/2 digits.

Step 4 − 取变量 Z = W – (U + V)，

Step 4 − Take a variable Z = W – (U + V),

其中，

where,

U = X1Y1, V = X2Y2
W = (X1 + X2) (Y1 + Y2), Z = X1Y2 + X2Y1.

Step 5 − 然后，在公式中替换值后获得乘积 P −

Step 5 − Then, the product P is obtained after substituting the values in the formula −

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 中。

Step 6 − Recursively call the algorithm by passing the sub problems (X1, Y1), (X2, Y2) and (X1 + X2, Y1 + Y2) separately. Store the returned values in variables U, V and W respectively.

Example

让我们使用 Karatsuba 方法解决上面提出的同一问题，1456 × 6533 −

Let us solve the same problem given above using Karatsuba method, 1456 × 6533 −

Karatsuba 方法采用分治法，将问题划分为多个子问题，并应用递归来简化乘法运算。

The Karatsuba method takes the divide and conquer approach by dividing the problem into multiple sub-problems and applies recursion to make the multiplication simpler.

Step 1

假设 n 是 2 的幂，以以下形式重写 n 位数 −

Assuming that n is the power of 2, rewrite the n-digit numbers in the form of −

X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2

我们得到，

That gives us,

1456 = 102(14) + 56
6533 = 102(65) + 33

首先让我们尝试简化数学表达式，我们得到，

First let us try simplifying the mathematical expression, we get,

(1400 × 6500) + (56 × 33) + (1400 × 33) + (6500 × 56) =
104 (14 × 65) + 102 [(14 × 33) + (56 × 65)] + (33 × 56)

因为相乘两个两位数比相乘两个四位数更容易求解，故上面的表达式是给定乘法问题的简化版本。

The above expression is the simplified version of the given multiplication problem, since multiplying two double-digit numbers can be easier to solve rather than multiplying two four-digit numbers.

然而，这对于人脑而言是正确的，但是对于系统编译器而言，上面的表达式仍然具有与普通朴素乘法相同的时间复杂度。因为它具有 4 个两位数 × 两位数乘法，所以所需时间复杂度为 −

However, that holds true for the human mind. But for the system compiler, the above expression still takes the same time complexity as the normal naive multiplication. Since it has 4 double-digit × double-digit multiplications, the time complexity taken would be −

14 × 65 → O(4)
14 × 33 → O(4)
65 × 56 → O(4)
56 × 33 → O(4)
= O (16)

因此，需要进一步简化计算。

Thus, the calculation needs to be simplified further.

Step 2

X = 1456
Y = 6533

因为 n 不等于 1，该算法跳到步骤 3。

Since n is not equal to 1, the algorithm jumps to step 3.

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2

我们得到，

That gives us,

1456 = 102(14) + 56
6533 = 102(65) + 33

计算 Z = W – (U + V) −

Calculate Z = W – (U + V) −

Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2)
Z = X1Y2 + X2Y1
Z = (14 × 33) + (65 × 56)

最终结果，

The final product,

P = 10n. U + 10n/2. Z + V
   = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2
   = 104 (14 × 65) + 102 [(14 × 33) + (65 × 56)] + (56 × 33)

子问题可进一步分解为更小的子问题；因此，该算法再次递归调用。

The sub-problems can be further divided into smaller problems; therefore, the algorithm is again called recursively.

Step 3

X1 和 Y1 作为参数 X 和 Y 进行传递。

X1 and Y1 are passed as parameters X and Y.

所以现在 X = 14，Y = 65

So now, X = 14, Y = 65

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
14 = 10(1) + 4
65 = 10(6) + 5

计算 Z = W – (U + V) −

Calculate 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)
   = 910

Step 4

X2 和 Y2 作为参数 X 和 Y 进行传递。

X2 and Y2 are passed as parameters X and Y.

所以现在 X = 56，Y = 33

So now, X = 56, Y = 33

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
56 = 10(5) + 6
33 = 10(3) + 3

计算 Z = W – (U + V) −

Calculate 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)
= 1848

Step 5

X1 + X2 和 Y1 + Y2 作为参数 X 和 Y 进行传递。

X1 + X2 and Y1 + Y2 are passed as parameters X and Y.

所以现在 X = 70，Y = 98

So now, X = 70, Y = 98

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2
70 = 10(7) + 0
98 = 10(9) + 8

计算 Z = W – (U + V) −

Calculate 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

最终结果，

The final product,

P = 10n. U + 10n/2. Z + V

U = 910
V = 1848
Z = W – (U + V) = 6860 – (1848 + 910) = 4102

将相应的值代入公式中，

Substituting the values in equation,

P = 10n. U + 10n/2. Z + V
P = 104 (910) + 102 (4102) + 1848
P = 91,00,000 + 4,10,200 + 1848
P = 95,12,048

Analysis

卡拉楚巴算法是一种递归算法；因为它在执行期间调用自己的较小实例。

The Karatsuba algorithm is a recursive algorithm; since it calls smaller instances of itself during execution.

根据该算法，它只对 n/2 位数字调用自己三次即可求得两个 n 位数字的最终乘积。

According to the algorithm, it calls itself only thrice on n/2-digit numbers in order to achieve the final product of two n-digit numbers.

现在，如果 T(n) 表示执行乘法时所需的数字乘法次数，

Now, if T(n) represents the number of digit multiplications required while performing the multiplication,

T(n) = 3T(n/2)

此方程是一个简单的递推关系，可解为：

This equation is a simple recurrence relation which can be solved as −

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 求解，因为我们有一个除法函数，形式为：

Recurrence relations can be solved using the master’s theorem, since we have a dividing function in the form of −

T(n) = aT(n/b) + f(n), where, a = 3, b = 2 and f(n) = 0
which leads to k = 0.

由于 f(n) 代表递归外部完成的工作，即卡拉楚巴中的加法和减法算术运算，这些算术运算不属于时间复杂度。

Since f(n) represents work done outside the recursion, which are addition and subtraction arithmetic operations in Karatsuba, these arithmetic operations do not contribute to time complexity.

检查“a”和“bk”之间的关系。

Check the relation between ‘a’ and ‘bk’.

a > bk = 3 > 20

根据大师定理，应用情况 1。

According to master’s theorem, apply case 1.

T(n) = O(nlogb a)
T(n) = O(nlog 3)

卡拉苏巴算法快速乘法的的时间复杂度为 O(nlog 3) 。

The time complexity of Karatsuba algorithm for fast multiplication is O(nlog 3).

Example

在卡拉苏巴算法的完整实现中，我们尝试将两个较大的数字相乘。此处，由于 long 数据类型在小数点后最多可接受 18 位，因此我们将输入作为 long 值。在获取最终乘积之前递归调用 Karatsuba 函数。

In the complete implementation of Karatsuba Algorithm, we are trying to multiply two higher-valued numbers. Here, since the long data type accepts decimals upto 18 places, we take the inputs as long values. The Karatsuba function is called recursively until the final product is obtained.