C++ 退出代码 3221225725，Karatsuba 乘法递归算法

Question

Karatsuba 乘法算法实现不输出任何结果并退出，代码=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) 检测基本情况，但基本情况应该在这些大小的 either 为 1 时启动，不需要两者。所以这应该是一个 || 运算符，或者应该写成两个单独的 if 语句。
应拆分输入字符串，使 b 和 d 的大小相等。这不是您的代码所做的。注意 Wikipedia article 是如何强调这一点的：

The second argument of the split_at function specifies the number of digits to extract from the right
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'));
}

C++ 退出代码 3221225725，Karatsuba 乘法递归算法

C++ exit code 3221225725, Karatsuba multiplication recursive algorithm

c++

algorithm

recursion