大整数乘法（Karatsuba 算法）——分治算法实现

---

🎯 问题描述：

给定两个非常大的整数（可能有几百位），如何高效地计算它们的乘积？

传统的竖式乘法时间复杂度为 O(n²)，当数字非常大时效率极低。我们可以使用分治思想来优化这个过程。

---

🧩 分治策略：Karatsuba 算法简介

基本思路：

将两个大整数 $x$ 和 $y$ 拆分成两部分：

$$x = a \cdot 10^m + b \\ y = c \cdot 10^m + d$$

那么：

$$x \cdot y = ac \cdot 10^{2m} + (ad + bc) \cdot 10^m + bd $$

如果直接计算，需要四次乘法（ac, ad, bc, bd）。但 Karatsuba 发现可以只用三次乘法：

• $A = ac$
• $B = bd$
• $C = (a + b)(c + d)$

然后：

$$x \cdot y = A \cdot 10^{2m} + (C - A - B) \cdot 10^m + B $$

这样就减少了乘法次数，从而提高效率！

---

💻 C++代码实现 + 注释：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 辅助函数：字符串左补零
string addLeadingZeros(string s, int n) {
    return string(n, '0') + s;
}

// 辅助函数：字符串加法
string addStrings(const string& a, const string& b) {
    string result;
    int i = a.size() - 1;
    int j = b.size() - 1;
    int carry = 0;

    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        result.push_back('0' + (sum % 10));
        carry = sum / 10;
    }

    reverse(result.begin(), result.end());
    return result;
}

// 辅助函数：字符串减法（假设 a >= b）
string subtractStrings(const string& a, const string& b) {
    string result;
    int i = a.size() - 1;
    int j = b.size() - 1;
    int borrow = 0;

    while (i >= 0) {
        int digitA = a[i] - '0';
        int digitB = (j >= 0) ? b[j] - '0' : 0;
        int diff = digitA - digitB - borrow;

        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }

        result.push_back('0' + diff);
        --i;
        --j;
    }

    // 去除前导0
    reverse(result.begin(), result.end());
    while (result.size() > 1 && result.back() == '0')
        result.pop_back();
    reverse(result.begin(), result.end());

    return result;
}

// 分治主函数：Karatsuba 算法
string karatsubaMultiply(const string& num1, const string& num2) {
    // 基本情况：一个数是0或空
    if (num1 == "0" || num2 == "0")
        return "0";
    if (num1.size() == 1 && num2.size() == 1)
        return to_string(stoi(num1) * stoi(num2));

    // 保证两个数一样长，不够前面补0
    int maxLen = max(num1.size(), num2.size());
    string a = addLeadingZeros(num1, maxLen - num1.size());
    string c = addLeadingZeros(num2, maxLen - num2.size());

    // 分成前后两半
    int mid = maxLen / 2;
    string aL = a.substr(0, maxLen - mid); // 左半部分
    string aR = a.substr(maxLen - mid);    // 右半部分
    string cL = c.substr(0, maxLen - mid);
    string cR = c.substr(maxLen - mid);

    // 递归计算三个乘积
    string A = karatsubaMultiply(aL, cL);
    string B = karatsubaMultiply(aR, cR);
    string C = karatsubaMultiply(addStrings(aL, aR), addStrings(cL, cR));

    // 计算中间项：C - A - B
    string D = subtractStrings(C, A);
    string middle = subtractStrings(D, B);

    // 补零操作
    string part1 = addLeadingZeros(A, 2 * mid); // A * 10^(2mid)
    string part2 = addLeadingZeros(middle, mid); // middle * 10^mid
    string part3 = B;                             // B

    // 合并结果
    string result = addStrings(part1, part2);
    result = addStrings(result, part3);

    return result;
}

int main() {
    string num1, num2;

    cout << "请输入第一个大整数（可含数百位）：";
    cin >> num1;
    cout << "请输入第二个大整数（可含数百位）：";
    cin >> num2;

    string result = karatsubaMultiply(num1, num2);

    cout << "乘积结果为：" << result << endl;

    return 0;
}

---

✅ 示例运行：

输入：

请输入第一个大整数（可含数百位）：123456789
请输入第二个大整数（可含数百位）：987654321

输出：

乘积结果为：121932631112635269

---

⏱️ 时间复杂度分析：

方法	时间复杂度
竖式乘法	O(n²)
Karatsuba 算法	O(n^log₂3) ≈ O(n^1.585)

Karatsuba 明显优于传统方法，尤其适用于非常大的整数乘法。

---

📌 进阶建议练习：

1. 实现更高效的乘法算法如 Toom-Cook 或 FFT 快速傅里叶变换乘法
2. 支持负数输入
3. 封装成类，支持重载运算符 *
4. 使用 vector 替代 string 提高性能

---

如果你希望我为你讲解：

• 如何使用 FFT 实现超大整数乘法
• 如何实现 大整数幂运算
• 如何封装成一个完整的 大整数类（BigInteger）

欢迎继续提问！我可以为你提供完整、详细的代码示例 😊