大数相乘：分治法 (Karatsuba 算法) 详解

大数相乘是指两个超出计算机整数范围的大数相乘的运算。分治法解决大数相乘的一种常见算法是 Karatsuba 算法。该算法基于分治的思想，通过将大数分割为较小的数，并利用乘法的性质来减少乘法运算的次数，从而提高算法的效率。

问题描述

输入两个数字字符串，输出这两个字符串对应的整型数相乘的结果。

输入格式

输入两个数字字符串

输出格式

输出这两个字符串对应的整型数相乘的结果

样例输入

123456789987654321 987654321123456789

样例输出

12193263113702179524102387545294031361

算法1：分治法 (Karatsuba 算法)

时间复杂度： O(n^(log_23))

Karatsuba 算法的本质思想是通过减少乘法的次数来提高效率。

通常我们计算两个 n 位数的积需要进行 n^2 次乘法运算，但是 Karatsuba 算法只需要进行 3 次乘法运算。

假设要计算两个 n 位数 x 和 y 的积，我们可以将其拆分成：

x = a * 10^(n/2) + b y = c * 10^(n/2) + d

则 xy 可以表示成：

xy = (a * 10^(n/2) + b) * (c * 10^(n/2) + d) = ac * 10^n + (ad + bc) * 10^(n/2) + bd

其中 ad+bc 可以通过下面的式子计算：

ad + bc = (a+b) * (c+d) - ac - bd

可以发现，我们只需要计算 3 个 n/2 位数的积就能得到 ad+bc，从而计算出 xy。

由于 Karatsuba 算法是递归的，因此需要一个终止条件。当计算的数的位数小于等于某个阈值时，我们直接使用普通的乘法即可。

C++ 代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string multiply(string num1, string num2) {
    if (num1.length() < num2.length()) {
        swap(num1, num2);
    }
    int n1 = num1.length(), n2 = num2.length();
    if (n1 == 0 || n2 == 0) {
        return "0";
    }
    if (n1 == 1 && n2 == 1) {
        return to_string(stoi(num1) * stoi(num2));
    }
    int mid = n1 / 2;
    string a = num1.substr(0, mid);
    string b = num1.substr(mid);
    string c = num2.substr(0, min(mid, n2));
    string d = num2.substr(min(mid, n2));
    string ac = multiply(a, c);
    string bd = multiply(b, d);
    string ad_bc = multiply(add(a, b), add(c, d));
    ad_bc = subtract(ad_bc, ac);
    ad_bc = subtract(ad_bc, bd);
    return add(add(multiply(ac, string(2 * mid, '0')), multiply(ad_bc, string(mid, '0'))), bd);
}

string add(string num1, string num2) {
    if (num1.length() < num2.length()) {
        swap(num1, num2);
    }
    int n1 = num1.length(), n2 = num2.length();
    string result = "";
    int carry = 0;
    for (int i = n1 - 1, j = n2 - 1; i >= 0 || j >= 0 || carry; i--, j--) {
        int sum = carry + (i >= 0 ? num1[i] - '0' : 0) + (j >= 0 ? num2[j] - '0' : 0);
        carry = sum / 10;
        result = to_string(sum % 10) + result;
    }
    return result;
}

string subtract(string num1, string num2) {
    if (num1.length() < num2.length()) {
        swap(num1, num2);
    }
    int n1 = num1.length(), n2 = num2.length();
    string result = "";
    int borrow = 0;
    for (int i = n1 - 1, j = n2 - 1; i >= 0 || j >= 0 || borrow; i--, j--) {
        int diff = (i >= 0 ? num1[i] - '0' : 0) - (j >= 0 ? num2[j] - '0' : 0) - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result = to_string(diff) + result;
    }
    return result;
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;
    cout << multiply(num1, num2) << endl;
    return 0;
}

算法2：暴力枚举

时间复杂度： O(n^2)

C++ 代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string multiply(string num1, string num2) {
    int n1 = num1.length(), n2 = num2.length();
    if (n1 == 0 || n2 == 0) {
        return "0";
    }
    string result(n1 + n2, '0');
    for (int i = n1 - 1; i >= 0; i--) {
        int carry = 0;
        for (int j = n2 - 1; j >= 0; j--) {
            int product = (num1[i] - '0') * (num2[j] - '0') + carry + (result[i + j + 1] - '0');
            result[i + j + 1] = (product % 10) + '0';
            carry = product / 10;
        }
        result[i] += carry;
    }
    for (int i = 0; i < result.length(); i++) {
        if (result[i] != '0') {
            return result.substr(i);
        }
    }
    return "0";
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;
    cout << multiply(num1, num2) << endl;
    return 0;
}

参考：