C++ 实现大数相乘算法

当我们需要计算两个超出计算机整数范围的大数相乘时，传统的计算方法已经无法满足需求，因此需要寻找一种适合大数相乘的算法。本文将介绍一种针对大数相乘的算法 - Karatsuba乘法，并使用C++语言进行实现。

Karatsuba 乘法的原理

Karatsuba 乘法的基本思想是将两个大数a和b分别划分为高位和低位，进而利用递归的方法将相乘转化为更小的数的相乘，最后统一合并得到最终结果。

假设a和b的长度相同，而且都是偶数，假设a实际上可以拆分为a0和a1两份，b可以拆分为b0和b1两份，即：

a = a0 * 10 ^ (n/2) + a1

b = b0 * 10 ^ (n/2) + b1

根据这个公式我们可以推导出Karatsuba算法的公式：

a * b = (a0 * 10 ^ (n/2) + a1) * (b0 * 10 ^ (n/2) + b1)

    = a0 * b0 * 10^n + (a0 * b1 + a1 * b0) * 10^(n/2) + a1 * b1

这样我们就将一个大的乘法问题转化为3个小的乘法问题，并且它们的结果都可以通过加、减的计算得出。同时这个算法只需要递归两次，即可得出结果。

Karatsuba乘法的优点在于它的运算次数比传统的算法要少，因此可以大大提高计算效率。

C++ 实现

下面是使用C++实现Karatsuba算法的代码：

#include<iostream>
#include<cstring>
using namespace std;

string add(string a, string b) {
    if(a.length() < b.length()) swap(a, b);
    int alen = a.length(), blen = b.length();
    int carry = 0;  // 进位 
    string res = "";
    for(int i=alen-1, j=blen-1; i>=0; i--, j--) {
        int k = i-j-1;
        int sum = (j>=0 ? (b[j]-'0') : 0) + carry + (a[i]-'0');
        res = char(sum % 10 + '0') + res;
        carry = sum / 10;
    }
    if(carry) res = char(carry+'0') + res;
    return res;
}

string sub(string a, string b) {
    int alen = a.length(), blen = b.length();
    int jw = 0;  // 借位 
    string res = "";
    for(int i=alen-1, j=blen-1; i>=0; i--, j--) {
        int k = i-j-1;
        int v = a[i] - jw - (j>=0 ? b[j]-'0' : 0);
        if(v < 0) {
            v += 10;
            jw = 1;
        } else {
            jw = 0;
        }
        res = char(v+'0') + res;
    }
    while(res[0] == '0' && res.length() > 1) res.erase(0,1);  // 去掉前导0 
    return res;
}

string karatsuba(string a, string b) {
    int alen = a.length(), blen = b.length();
    if(alen < blen) {
        swap(alen, blen);
        swap(a, b);
    }

    if(alen == 0) return "0";
    if(alen == 1) return to_string((a[0]-'0') * (b[0]-'0'));

    int llen = alen >> 1, rlen = alen - llen;
    string a0 = a.substr(0, llen), a1 = a.substr(llen, rlen);
    string b0 = b.substr(0, min(blen, llen)), b1 = b.substr(min(blen, llen), max(0, blen-llen));
    string z0 = karatsuba(a1, b1), z1 = karatsuba(add(a0, a1), add(b0, b1)), z2 = karatsuba(a0, b0);

    string res = add(z2, add(z0, sub(z1, add(z2, z0))));
    while(res[0] == '0' && res.length() > 1) res.erase(0, 1);  // 去掉前导0
    return res;
}

int main() {
    string a, b;
    while(cin >> a >> b) {
        string res = karatsuba(a, b);
        cout << res << endl;
    }
    return 0;
}

代码中我们定义了Karatsuba算法的 karatsuba 函数，用来实现大数的相乘。同时我们还定义了加法 add 和减法 sub 的函数，这是因为在Karatsuba算法的实现中我们需要将大数的相加和相减。程序的输入为两个大数，即字符串类型的 a 和 b，程序的输出为两个大数的乘积，即字符串类型的 res。

示例

示例1

输入：

12345678901234567890
10101010101010101010

输出：

12499999991234567910027182807451020480

示例2

输入：

9999999999
8888888888

输出：

88888888871111111112

总结

本文介绍了Karatsuba乘法的基本原理，同时使用C++实现了该算法。本文同时提供了两个用例来说明算法的正确性。这个算法在大数相乘的场景下应用广泛，可以帮助我们提高相乘的计算效率。