c++退出代码3221225725,Karatsuba乘法递归算法

Question

Karatsuba乘法算法实现不输出任何结果，以code=3221225725退出。

下面是终端显示的信息:

[Running] cd "d:algorithms_cpp" && g++ karatsube_mul.cpp -o karatsube_mul && "d:algorithms_cpp"karatsube_mul
[Done] exited with code=3221225725 in 1.941 seconds

代码如下:

#include <bits/stdc++.h>
using namespace std;
string kara_mul(string n, string m)
{
int len_n = n.size();
int len_m = m.size();
if (len_n == 1 && len_m == 1)
{
return to_string((stol(n) * stol(m)));
}
string a = n.substr(0, len_n / 2);
string b = n.substr(len_n / 2);
string c = m.substr(0, len_m / 2);
string d = m.substr(len_m / 2);
string p1 = kara_mul(a, c);
string p2 = kara_mul(b, d);
string p3 = to_string((stol(kara_mul(a + b, c + d)) - stol(p1) - stol(p2)));
return to_string((stol(p1 + string(len_n, '0')) + stol(p2) + stol(p3 + string(len_n / 2, '0'))));
}
int main()
{
cout << kara_mul("15", "12") << "n";
return 0;
}

在解决这个问题之后，我还想知道如何使用这种技术将两个664位的整数相乘。

Answer 1

有几个问题:

• 你得到的异常是由无限递归在这个调用引起的:

  kara_mul(a + b, c + d)
  

  由于这些变量都是字符串，因此+是字符串拼接。这意味着这些参数的值为n和m，它们是函数当前执行的参数。

  正确的算法应该在这里执行数值加法，为此您需要提供一个实现(添加两个可能非常长的整数的字符串表示形式)

• if (len_n == 1 && len_m == 1)检测基本情况，但是当其中一个为1时，基本情况应该启动，而不必两个。因此，这应该是一个||操作符，或者应该写成两个单独的if语句。

• 输入字符串应该分割，使b和d的大小相等。这不是您的代码所做的。请注意维基百科文章是如何强调这一点的:

  split_at函数的第二个参数指定从右

  中提取的位数。

• stol不应该在可能太长而无法转换为long的字符串上调用。例如，stol(p1)是不安全的，因为p1可能有20个或更多的数字。

• 作为上一点的结果，您需要实现两个字符串表示形式的加法或减法函数，以及一个可以将字符串表示形式与单个数字(基数)相乘的函数。

下面是纠正这些问题的实现:

#include <iostream>
#include <algorithm> 
int digit(std::string n, int i) {
return i >= n.size() ? 0 : n[n.size() - i - 1] - '0';
}
std::string add(std::string n, std::string m) {
int len = std::max(n.size(), m.size());
std::string result;
int carry = 0;
for (int i = 0; i < len; i++) {
int sum = digit(n, i) + digit(m, i) + carry; 
result += (char) (sum % 10 + '0');
carry = sum >= 10;
}
if (carry) result += '1';
reverse(result.begin(), result.end());
return result;
}
std::string subtract(std::string n, std::string m) {
int len = n.size();
if (m.size() > len) throw std::invalid_argument("subtraction overflow");
if (n == m) return "0";
std::string result;
int carry = 0;
for (int i = 0; i < len; i++) {
int diff = digit(n, i) - digit(m, i) - carry;
carry = diff < 0;
result += (char) (diff + carry * 10 + '0');
}
if (carry) throw std::invalid_argument("subtraction overflow");
result.erase(result.find_last_not_of('0') + 1);
reverse(result.begin(), result.end());
return result;
}
std::string simple_mul(std::string n, int coefficient) {
if (coefficient < 2) return coefficient ? n : "0";
std::string result = simple_mul(add(n, n), coefficient / 2);
return coefficient % 2 ? add(result, n) : result;
}
std::string kara_mul(std::string n, std::string m) {
int len_n = n.size();
int len_m = m.size();
if (len_n == 1) return simple_mul(m, digit(n, 0));
if (len_m == 1) return simple_mul(n, digit(m, 0));
int len_min2 = std::min(len_n, len_m) / 2; 
std::string a = n.substr(0, len_n - len_min2);
std::string b = n.substr(len_n - len_min2);
std::string c = m.substr(0, len_m - len_min2);
std::string d = m.substr(len_m - len_min2);
std::string p1 = kara_mul(a, c);
std::string p2 = kara_mul(b, d);
std::string p3 = subtract(kara_mul(add(a, b), add(c, d)), add(p1, p2));
return add(add(p1 + std::string(len_min2*2, '0'), p2), p3 + std::string(len_min2, '0'));
}