c++ - Karatsuba 整数乘法因段错误而失败

Question

当我运行程序时，它因段错误而崩溃。另外，当我在 codeblocks IDE 中调试代码时，我也无法调试它。程序甚至在调试开始之前就崩溃了。我无法理解这个问题。任何帮助，将不胜感激。谢谢!!

#include <iostream>
#include <math.h>
#include <string>
using namespace std;

// Method to make strings of equal length
int makeEqualLength(string& fnum,string& snum){
    int l1 = fnum.length();
    int l2 = snum.length();
    if(l1>l2){
        int d = l1-l2;
        while(d>0){
            snum  = '0' + snum;
            d--;
        }
        return l1;
    }
    else if(l2>l1){
        int d = l2-l1;
        while(d>0){
            fnum  = '0' + fnum;
            d--;
        }
        return l2;
    }
    else
        return l1;
}

int singleDigitMultiplication(string& fnum,string& snum){
    return ((fnum[0] -'0')*(snum[0] -'0'));
}

string addStrings(string& s1,string& s2){
  int length = makeEqualLength(s1,s2);
  int carry = 0;
  string result;
  for(int i=length-1;i>=0;i--){
    int fd = s1[i]-'0';
    int sd = s2[i]-'0';
    int sum = (fd+sd+carry)%10+'0';
    carry = (fd+sd+carry)/10;
    result = (char)sum + result;
  }
  result = (char)carry + result;
  return result;
}

long int multiplyByKaratsubaMethod(string fnum,string snum){

    int length = makeEqualLength(fnum,snum);
    if(length==0) return 0;
    if(length==1) return singleDigitMultiplication(fnum,snum);

    int fh = length/2;
    int sh = length - fh;

    string Xl = fnum.substr(0,fh);
    string Xr = fnum.substr(fh,sh);
    string Yl = snum.substr(0,fh);
    string Yr = snum.substr(fh,sh);

    long int P1 = multiplyByKaratsubaMethod(Xl,Yl);
    long int P3 = multiplyByKaratsubaMethod(Xr,Yr);
    long int P2 = multiplyByKaratsubaMethod(addStrings(Xl,Xr),addStrings(Yl,Yr)) - P1-P3;

    return (P1*pow(10,length) + P2*pow(10,length/2) + P3);
}


int main()
{
    string firstNum = "62";
    string secondNum = "465";
    long int result = multiplyByKaratsubaMethod(firstNum,secondNum);
    cout << result << endl;
    return 0;
}

Answer 1

您的代码中存在三个严重问题:

1. result = (char)carry + result; 不起作用。
   进位的值介于 0 (0 * 0) 和 8 (9 * 9) 之间。它必须转换为相应的 ASCII 值:
   result = (char)(carry + '0') + result; 。

2. 这会导致下一个问题:如果进位是 0，进位也会被插入。缺少 if 语句:
   if (carry/* != 0*/) result = (char)(carry + '0') + result; 。

3. 修复前两个问题后再次测试，还是出现栈溢出。所以，我将你的算法与我通过谷歌找到的另一个算法进行了比较:
   Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication)
   (可能是你的来源，因为它看起来非常相似)。没有深入挖掘，我修复了一个看似简单的传输错误:
   return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
   (我将 length 替换为 2 * sh，将 length/2 替换为 sh，就像我在 google 代码中看到的那样。)这对我来说很明显长度可以有奇数的调试器，因此 sh 和 length/2 是不同的值。

之后，您的程序开始运行。

我更改了 main() 函数以对其进行更严格的测试:

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

string intToStr(int i)
{
  string text;
  do {
    text.insert(0, 1, i % 10 + '0');
    i /= 10;
  } while (i);
  return text;
}

// Method to make strings of equal length
int makeEqualLength(string &fnum, string &snum)
{
  int l1 = (int)fnum.length();
  int l2 = (int)snum.length();
  return l1 < l2
    ? (fnum.insert(0, l2 - l1, '0'), l2)
    : (snum.insert(0, l1 - l2, '0'), l1);
}

int singleDigitMultiplication(const string& fnum, const string& snum)
{
  return ((fnum[0] - '0') * (snum[0] - '0'));
}

string addStrings(string& s1, string& s2)
{
  int length = makeEqualLength(s1, s2);
  int carry = 0;
  string result;
  for (int i = length - 1; i >= 0; --i) {
    int fd = s1[i] - '0';
    int sd = s2[i] - '0';
    int sum = (fd + sd + carry) % 10 + '0';
    carry = (fd + sd + carry) / 10;
    result.insert(0, 1, (char)sum);
  }
  if (carry) result.insert(0, 1, (char)(carry + '0'));
  return result;
}

long int multiplyByKaratsubaMethod(string fnum, string snum)
{
  int length = makeEqualLength(fnum, snum);
  if (length == 0) return 0;
  if (length == 1) return singleDigitMultiplication(fnum, snum);

  int fh = length / 2;
  int sh = length - fh;

  string Xl = fnum.substr(0, fh);
  string Xr = fnum.substr(fh, sh);
  string Yl = snum.substr(0, fh);
  string Yr = snum.substr(fh, sh);

  long int P1 = multiplyByKaratsubaMethod(Xl, Yl);
  long int P3 = multiplyByKaratsubaMethod(Xr, Yr);
  long int P2
    = multiplyByKaratsubaMethod(addStrings(Xl, Xr), addStrings(Yl, Yr))
    - P1 - P3;
  return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
}

int main()
{
  int nErrors = 0;
  for (int i = 0; i < 1000; i += 3) {
    for (int j = 0; j < 1000; j += 3) {
      long int result
        = multiplyByKaratsubaMethod(intToStr(i), intToStr(j));
      bool ok = result == i * j;
      cout << i << " * " << j << " = " << result
        << (ok ? " OK." : " ERROR!") << endl;
      nErrors += !ok;
    }
  }
  cout << nErrors << " error(s)." << endl;
  return 0;
}

关于我所做更改的注释:

1. 关于 std 库:请不要将 header 与“.h”和不带“.h”混合使用。 std 库的每个 header 都以“非后缀风格”提供。 (带“.h”的头文件要么是 C 头文件，要么是老式的。)C 库的头文件已适应 C++。它们的旧名称带有前缀“c”，没有后缀“.h”。
   因此，我将 #include <math.h> 替换为 #include <cmath> 。

2. 我忍不住要让 makeEqualLength() 短一点。

3. 请注意，std 中的许多方法使用 std::size_t 而不是 int 或 unsigned 。 std::size_t 具有适当的宽度来进行数组下标和指针运算，即它具有“机器字宽度”。我相信很长一段时间 int 和 unsigned 也应该有“机器字宽”并且不关心 size_t 。当我们在 Visual Studio 中从 x86(32 位)更改为 x64(64 位)时，我发现自己错得很惨:std::size_t 现在是 64 位，但 int 和 unsigned 仍然是 32 位。 (MS VC++ 也不异常(exception)。其他编译器供应商(但不是全部)也采用相同的方式。)
   我插入了一些 C 类型转换以从编译器输出中删除警告。此类用于删除警告的强制转换(无论您使用 C 强制转换还是更好的 C++ 强制转换)应始终谨慎使用，并应理解为确认:亲爱的编译器。我看到你有顾虑，但我(相信)知道并向你保证它应该会正常工作。

4. 我不确定您打算在某些地方使用 long int。 (可能你从原始源转移了这段代码而不关心。)你肯定知道，所有 int 类型的实际大小可能不同，以匹配目标平台的最佳性能。我正在使用 Visual Studio 在装有 Windows 10 的英特尔 PC 上工作。 sizeof (int) == sizeof (long int)(32 位)。这与我编译 x86 代码(32 位)还是 x64 代码(64 位)无关。 gcc(在我的例子中是在 cygwin 上)以及任何带有 Linux 的 Intel-PC(AFAIK)也是如此。对于比 int 更大的类型，您必须选择 long long int。

我在 Windows 10(64 位)上的 cygwin 中完成了示例 session :

$ g++ -std=c++11 -o karatsuba karatsuba.cc 

$ ./karatsuba
0 * 0 = 0 OK.
0 * 3 = 0 OK.
0 * 6 = 0 OK.

等等

999 * 993 = 992007 OK.
999 * 996 = 995004 OK.
999 * 999 = 998001 OK.
0 error(s).

$