Karatsuba 算法

更新于 2025/10/16 16:21:06

Karatsuba 算法
分析
示例

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

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

为了更好地理解这种乘法，我们考虑两个四位数整数：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 = 10^n/2X₁ + X₂
Y = 10^n/2Y₁ + Y₂

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

步骤 4 − 取变量 Z = W – (U + V)

其中，

U = X₁Y₁，V = X₂Y₂
W = (X₁ + X₂) (Y₁ + Y₂)，Z = X₁Y₂ + X₂Y₁。

步骤 5 −然后，将公式中的值代入 − 中，得到乘积 P。

P = 10ⁿ(U) + 10n/2(Z) + V
P = 10ⁿ (X₁Y₁) + 10n/2 (X₁Y₂ + X₂Y₁) + X₂Y₂。

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

示例

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

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

步骤 1

假设 n 是 2 的幂，将 n 位数字重写为 − 的形式。

X = 10^n/2X₁ + X₂ Y = 10^n/2Y₁ + Y₂

得出：

1456 = 10²(14) + 56
6533 = 10²(65) + 33

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

(1400 × 6500) + (56 × 33) + (1400 × 33) + (6500 × 56) = 
10⁴ (14 × 65) + 10² [(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 = 10^n/2X₁ + X₂
Y = 10^n/2Y₁ + Y₂

由此可得：

1456 = 10²(14) + 56
6533 = 10²(65) + 33

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

Z = (X₁ + X₂) (Y₁ + Y₂) – (X₁Y₁ + X₂Y₂)
Z = X₁Y₂ + X₂Y₁
Z = (14 × 33) + (65 × 56)

最终结果

P = 10ⁿ. U + 10^n/2. Z + V 
   = 10ⁿ (X₁Y₁) + 10^n/2 (X₁Y₂ + X₂Y₁) + X₂Y₂ 
   = 10⁴ (14 × 65) + 10² [(14 × 33) + (65 × 56)] + (56 × 33)

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

步骤 3

X₁ 和 Y₁ 作为参数 X 和 Y 传递。

因此，X = 14，Y = 65

X = 10^n/2X₁ + X₂
Y = 10^n/2Y₁ + Y₂
14 = 10(1) + 4
65 = 10(6) + 5

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

Z = (X₁ + X₂) (Y₁ + Y₂) – (X₁Y₁ + X₂Y₂) 
Z = X₁Y₂ + X₂Y₁ 
Z = (1 × 5) + (6 × 4) = 29 

P = 10ⁿ (X₁Y₁) + 10^n/2 (X₁Y₂ + X₂Y₁) + X₂Y₂ 
   = 10² (1 × 6) + 101 (29) + (4 × 5) 
   = 910

步骤 4

X₂ 和 Y₂ 作为参数 X 和 Y 传递。

因此，X = 56，Y = 33

X = 10^n/2X₁ + X₂
Y = 10^n/2Y₁ + Y₂
56 = 10(5) + 6
33 = 10(3) + 3

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

Z = (X₁ + X₂) (Y₁ + Y₂) – (X₁Y₁ + X₂Y₂)
Z = X₁Y₂ + X₂Y₁
Z = (5 × 3) + (6 × 3) = 33

P = 10ⁿ (X₁Y₁) + 10^n/2 (X₁Y₂ + X₂Y₁) + X₂Y₂
= 10² (5 × 3) + 101 (33) + (6 × 3)
= 1848

步骤 5

X₁ + X₂ 和 Y₁ + Y₂ 作为参数 X 和 Y 传递。

因此，X = 70，Y = 98

X = 10^n/2X₁ + X₂ 
Y = 10^n/2Y₁ + Y₂ 
70 = 10(7) + 0 
98 = 10(9) + 8

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

Z = (X₁ + X₂) (Y₁ + Y₂) – (X₁Y₁ + X₂Y₂)
Z = X₁Y₂ + X₂Y₁
Z = (7 × 8) + (0 × 9) = 56

P = 10ⁿ (X₁Y₁) + 10^n/2 (X₁Y₂ + X₂Y₁) + X₂Y₂
= 10² (7 × 9) + 101 (56) + (0 × 8)
=

步骤 6

最终结果

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

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

代入公式中的值，

P = 10ⁿ. U + 10^n/2. Z + V
P = 10⁴ (910) + 10² (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)

该等式是一个简单的递归关系，可以解为 −

将 T(n/2) = 3T(n/4) 代入上述等式，可得：
T(n) = 9T(n/4)
T(n) = 27T(n/8)
T(n) = 81T(n/16)
.
.
.
.
T(n) = 3ⁱ T(n/2ⁱ) 是 Karatsuba 算法的递归关系的一般形式。

递归关系可以使用大师定理求解，因为我们有一个形式为 − 的除法函数。

T(n) = aT(n/b) + f(n)，其中 a = 3，b = 2，f(n) = 0
从而得出 k = 0。

由于 f(n) 表示递归之外的工作，这些工作在 Karatsuba 中属于加减算术运算，因此这些算术运算不会增加时间复杂度。

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

a > b^k = 3 > 2⁰

根据大师定理，应用案例 1。

T(n) = O(n^{logb a})
T(n) = O(n^{log 3})

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

示例

在 Karatsuba 算法的完整实现中，我们尝试将两个数值较高的数字相乘。由于 long 数据类型最多可容纳 18 位小数，因此我们将输入视为 long 值。Karatsuba 函数将递归调用，直到获得最终乘积。

C C++ Java Python

#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;
   
   // 确定 X 和 Y 的大小
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;
   
   // 将最大长度向上舍入
   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
", 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;

   // 确定 X 和 Y 的大小
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;

   // 将最大长度向上舍入
   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;
      // 确定 X 和 Y 的大小
      int size = Math.max(get_size(X), get_size(Y));
      if(size < 10)
         return X * Y;
      // 将最大长度向上舍入
      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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

Karatsuba 算法

Karatsuba 算法

示例

分析

示例

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！