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

$