Karatsuba 算法

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

通常的乘法方法需要 n² 次计算才能得到最终乘积，因为必须对两个数字中的所有数字组合进行乘法运算，然后将子乘积相加得到最终乘积。这种乘法方法称为朴素乘法。

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

所以，1456 × 6533 =？

在这种朴素乘法方法中，由于两个数字的位数都是 4，因此会执行 16 次一位数 × 一位数的乘法。因此，这种方法的时间复杂度为 O(4²)，因为它需要 4² 步才能计算出最终乘积。

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

Karatsuba 算法

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

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

步骤 1 - 在此算法中，我们假设 n 是 2 的幂。

步骤 2 - 如果 n = 1，则我们使用乘法表查找 P = XY。

步骤 3 - 如果 n > 1，则将 n 位数字分成两半，并使用以下公式表示数字：

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

其中，X₁、X₂、Y₁、Y₂ 各有 n/2 位数字。

步骤 4 - 取一个变量 Z = W – (U + V)，

其中，

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

步骤 5 - 然后，在公式中代入值后得到乘积 P：

P = 10n(U) + 10n/2(Z) + V
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2.

步骤 6 - 通过分别传递子问题 (X₁, Y₁)、(X₂, Y₂) 和 (X₁ + X₂, Y₁ + Y₂) 来递归调用算法。将返回值分别存储在变量 U、V 和 W 中。

示例

让我们使用 Karatsuba 方法解决上面给出的相同问题，1456 × 6533：

Karatsuba 方法采用分治法，将问题分解成多个子问题，并应用递归使乘法更简单。

步骤 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)

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

步骤 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)

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

步骤 3

X₁ 和 Y₁ 作为参数 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) 
   = 910

步骤 4

X₂ 和 Y₂ 作为参数 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) 
= 1848

步骤 5

X₁ + X₂ 和 Y₁ + Y₂ 作为参数 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) 
=

步骤 6

最终乘积：

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

U = 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,048

分析

Karatsuba 算法是一个递归算法；因为它在执行期间调用自身较小的实例。

根据该算法，它只在 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.

可以使用主定理求解递推关系，因为我们有一个形式为的划分函数：

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

由于 f(n) 表示递归外部完成的工作，即 Karatsuba 中的加法和减法算术运算，这些算术运算不会影响时间复杂度。

检查 'a' 和 'b^k' 之间的关系。

a > bk = 3 > 20

根据主定理，应用情况 1。

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

Karatsuba 算法快速乘法的时间复杂度为O(n^{log 3})。

示例

在 Karatsuba 算法的完整实现中，我们试图乘以两个较大的数字。这里，由于long 数据类型最多接受 18 位小数，我们将输入作为long 值。Karatsuba 函数被递归调用，直到获得最终乘积。

#include <stdio.h>
#include <math.h>
int get_size(long);
long karatsuba(long X, long Y){
   
   // Base Case
   if (X < 10 && Y < 10)
      return X * Y;
   
   // determine the size of X and Y
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;
   
   // rounding up the max length
   size = (size/2) + (size%2);
   long multiplier = pow(10, size);
   long b = X/multiplier;
   long a = X - (b * multiplier);
   long d = Y / multiplier;
   long c = Y - (d * size);
   long u = karatsuba(a, c);
   long z = karatsuba(a + b, c + d);
   long v = karatsuba(b, d);
   return u + ((z - u - v) * multiplier) + (v * (long)(pow(10, 2 * size)));
}
int get_size(long value){
   int count = 0;
   while (value > 0) {
      count++;
      value /= 10;
   }
   return count;
}
int main(){

   // two numbers
   long x = 145623;
   long y = 653324;
   printf("The final product is: %ld\n", karatsuba(x, y));
   return 0;
}

The final product is: 95139000852

#include <iostream>
#include <cmath>
using namespace std;
int get_size(long);
long karatsuba(long X, long Y){

   // Base Case
   if (X < 10 && Y < 10)
      return X * Y;

   // determine the size of X and Y
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;

   // rounding up the max length
   size = (size/2) + (size%2);
   long multiplier = pow(10, size);
   long b = X/multiplier;
   long a = X - (b * multiplier);
   long d = Y / multiplier;
   long c = Y - (d * size);
   long u = karatsuba(a, c);
   long z = karatsuba(a + b, c + d);
   long v = karatsuba(b, d);
   return u + ((z - u - v) * multiplier) + (v * (long)(pow(10, 2 * size)));
}
int get_size(long value){
   int count = 0;
   while (value > 0) {
      count++;
      value /= 10;
   }
   return count;
}
int main(){

   // two numbers
   long x = 145623;
   long y = 653324;
   cout << "The final product is: " << karatsuba(x, y) << endl;
   return 0;
}

The final product is: 95139000852

import java.io.*;
public class Main {
   static long karatsuba(long X, long Y) {
      // Base Case
      if (X < 10 && Y < 10)
         return X * Y;
      // determine the size of X and Y
      int size = Math.max(get_size(X), get_size(Y));
      if(size < 10)
         return X * Y;
      // rounding up the max length
      size = (size/2) + (size%2);
      long multiplier = (long)Math.pow(10, size);
      long b = X/multiplier;
      long a = X - (b * multiplier);
      long d = Y / multiplier;
      long c = Y - (d * size);
      long u = karatsuba(a, c);
      long z = karatsuba(a + b, c + d);
      long v = karatsuba(b, d);
      return u + ((z - u - v) * multiplier) + (v * (long)(Math.pow(10, 2 * size)));
   }
   static int get_size(long value) {
      int count = 0;
      while (value > 0) {
         count++;
         value /= 10;
      }
      return count;
   }
   public static void main(String args[]) {
      // two numbers
      long x = 145623;
      long y = 653324;
      System.out.print("The final product is: ");
      long product = karatsuba(x, y);
      System.out.println(product);
   }
}

The final product is: 95139000852

import math
def karatsuba(X, Y):
    if X < 10 and Y < 10:
        return X * Y
    size = max(get_size(X), get_size(Y))
    if size < 10:
        return X * Y
    size = (size // 2) + (size % 2)
    multiplier = 10 ** size
    b = X // multiplier
    a = X - (b * multiplier)
    d = Y // multiplier
    c = Y - (d * size)
    u = karatsuba(a, c)
    z = karatsuba(a + b, c + d)
    v = karatsuba(b, d)
    return u + ((z - u - v) * multiplier) + (v * (10 ** (2 * size)))
def get_size(value):
    count = 0
    while value > 0:
        count += 1
        value //= 10
    return count
x = 145623
y = 653324
print("The final product is: ", end="")
product = karatsuba(x, y)
print(product)

The final product is: 95139000852