Karatsuba整数乘法失败和分段错误

Question

当我运行程序时，它崩溃与分段错误。另外，当我在代码块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. 在修复了前两个问题并再次测试之后，仍然发生堆栈溢出。因此，我将您的算法与Google找到的另一个算法进行了比较：
   Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication)
   （并且可能是您的起源，因为它看起来非常相似）。如果没有更深的挖掘，我定什么看起来像一个简单的传输错误：（我的2 * sh和length/2取代length通过sh就像我看到它在谷歌搜索代码）
   return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
   这对我来说变得明显在调试器中看到该长度可以有奇数值，因此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库：请不要混合头与“.h”和没有。 std图书馆的每个标题都以“非后缀风味”形式提供。 （带“.h”的头文件或者是C头文件或者老式的头文件。）C库的头文件已经适用于C++。它们的旧名称前缀为“c”，没有后缀“.h”。
   因此，我用#include <cmath>替换#include <math.h>。

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

3. 请注意，在std很多方法使用std::size_t代替int或unsigned。 std::size_t有适当的宽度来做数组下标和指针算术，即它具有“机器字宽度”。我相信很长一段时间，int和unsigned也应该有“机器宽度”也不在乎size_t。当我们将Visual Studio从x86（32位）更改为64位（64位）时，我学到了很糟糕的方式：std::size_t现在是64位，但int和unsigned仍然是32位。（MS VC++不是一个例外，其他编译器厂商（但不是全部）也是这样做的。）
   我插入了一些C类型转换以从编译器输出中删除警告。此类强制删除警告（无论您使用C强制类型还是更好地使用C++强制转换）应始终小心使用，并应理解为确认：亲爱的编译器。我看到你有问题，但我（相信）知道并向你保证它应该可以正常工作。

4. 我不确定您是否打算在某些地方使用long int。 （很可能，您从原始来源转移此代码而不关心。）您肯定知道，所有int类型的实际大小可能有所不同，以匹配目标平台的最佳性能。我正在使用Visual Studio开发带有Windows 10的Intel-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的示例会话：

$ 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). 

$