C++如何进行大整数的快速乘法（Karatsuba算法）？

大整数乘法是很多涉及高精度计算的场景下的核心需求，当参与运算的整数位数超过内置整型的取值范围时，就需要通过字符串或者数组模拟乘法运算。常规的逐位相乘算法时间复杂度为O(n²)，当整数位数较多时性能会明显下降，Karatsuba算法基于分治思想对乘法过程进行优化，能将时间复杂度降低到O(n^log2(3))，约为O(n^1.585)，在C++中实现该算法可以高效处理大整数乘法问题。

Karatsuba算法的核心原理

Karatsuba算法的核心是将两个大整数拆分，减少乘法运算的次数。假设我们有两个n位的大整数x和y，将每个数拆分为两部分：

• x = a * 10^m + b，其中m为n/2（取整）
• y = c * 10^m + d，其中m为n/2（取整）

常规计算x*y的结果为：x*y = a*c*10^(2m) + (a*d + b*c)*10^m + b*d，这里需要4次乘法运算。Karatsuba算法通过引入中间变量z = (a+b)*(c+d)，将a*d + b*c转化为z - a*c - b*d，这样只需要计算a*c、b*d、z这3次乘法，减少了一次乘法运算，这就是分治优化的核心。

C++实现的关键步骤

实现Karatsuba算法需要处理几个基础问题：大整数的表示、补零对齐、加法和减法运算、拆分与合并结果。我们用字符串来表示大整数，首先实现大整数的加法、减法（处理非负整数）以及补零函数。

基础辅助函数实现

首先是补零函数，用于将较短的字符串前面补零，让两个字符串长度一致，方便拆分：

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

// 字符串补零，让两个字符串长度相同，在较短的字符串前面加0
string addLeadingZeros(string num, int length) {
    while (num.length() < length) {
        num = "0" + num;
    }
    return num;
}

// 大整数加法，处理两个非负整数字符串的相加
string addStrings(string num1, string num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;
    string result = "";
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        result.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(result.begin(), result.end());
    // 去除前导零，避免结果为0时保留多余的0
    size_t startPos = result.find_first_not_of('0');
    if (startPos == string::npos) return "0";
    return result.substr(startPos);
}

// 大整数减法，假设num1 >= num2，处理非负整数字符串的相减
string subtractStrings(string num1, string num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int borrow = 0;
    string result = "";
    while (i >= 0) {
        int diff = (num1[i] - '0') - borrow;
        if (j >= 0) diff -= (num2[j] - '0');
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result.push_back(diff + '0');
        i--;
        j--;
    }
    reverse(result.begin(), result.end());
    // 去除前导零
    size_t startPos = result.find_first_not_of('0');
    if (startPos == string::npos) return "0";
    return result.substr(startPos);
}

Karatsuba算法核心实现

接下来实现Karatsuba乘法的核心逻辑，首先处理递归的终止条件：如果两个数中有一个长度小于等于1，直接用常规逐位乘法计算，避免递归过深。拆分时如果两个数字长度不一致，先补零到相同长度，再按一半长度拆分。

// Karatsuba大整数乘法核心函数
string karatsubaMultiply(string x, string y) {
    // 去除前导零
    size_t xStart = x.find_first_not_of('0');
    size_t yStart = y.find_first_not_of('0');
    if (xStart == string::npos) x = "0";
    else x = x.substr(xStart);
    if (yStart == string::npos) y = "0";
    else y = y.substr(yStart);

    // 如果有乘数为0，直接返回0
    if (x == "0" || y == "0") return "0";

    // 递归终止条件：位数小于等于1时直接相乘
    if (x.length() == 1 && y.length() == 1) {
        int res = (x[0] - '0') * (y[0] - '0');
        return to_string(res);
    }

    // 让两个数字长度相同，补前导零
    int maxLen = max(x.length(), y.length());
    x = addLeadingZeros(x, maxLen);
    y = addLeadingZeros(y, maxLen);

    // 拆分点，取长度的一半
    int m = maxLen / 2;
    // 拆分x为a和b，拆分y为c和d
    string a = x.substr(0, maxLen - m);
    string b = x.substr(maxLen - m);
    string c = y.substr(0, maxLen - m);
    string d = y.substr(maxLen - m);

    // 计算三次乘法
    string ac = karatsubaMultiply(a, c);
    string bd = karatsubaMultiply(b, d);
    // 计算(a+b)和(c+d)
    string aPlusB = addStrings(a, b);
    string cPlusD = addStrings(c, d);
    string z = karatsubaMultiply(aPlusB, cPlusD);
    // 计算ad + bc = z - ac - bd
    string adPlusBc = subtractStrings(subtractStrings(z, ac), bd);

    // 合并结果：ac * 10^(2m) + adPlusBc * 10^m + bd
    // 先给ac后面补2m个零
    string acWithZeros = ac + string(2 * m, '0');
    // 给adPlusBc后面补m个零
    string adBcWithZeros = adPlusBc + string(m, '0');

    // 相加得到最终结果
    string result = addStrings(addStrings(acWithZeros, adBcWithZeros), bd);
    return result;
}

测试代码

最后编写测试代码验证算法正确性：

int main() {
    // 测试案例1：普通大整数相乘
    string num1 = "123456789";
    string num2 = "987654321";
    string result1 = karatsubaMultiply(num1, num2);
    cout << num1 << " * " << num2 << " = " << result1 << endl;

    // 测试案例2：位数不同的整数相乘
    string num3 = "9999";
    string num4 = "888888";
    string result2 = karatsubaMultiply(num3, num4);
    cout << num3 << " * " << num4 << " = " << result2 << endl;

    // 测试案例3：包含零的情况
    string num5 = "12345";
    string num6 = "0";
    string result3 = karatsubaMultiply(num5, num6);
    cout << num5 << " * " << num6 << " = " << result3 << endl;

    return 0;
}

算法复杂度与优化说明

Karatsuba算法的时间复杂度为O(n^log2(3))，相比常规O(n²)的算法，在n较大时优势明显。实际实现中，当数字位数较小时，递归带来的开销可能会抵消算法本身的性能优势，可以在递归到数字位数小于某个阈值（比如32位）时，切换为常规乘法，进一步提升实际运行效率。另外，对于负数的处理可以在函数入口先记录符号，将数字转为正数后计算，最后根据符号规则添加负号即可。

Karatsuba算法C++大整数乘法分治算法修改时间：2026-06-18 13:57:56