karatsuba乘法，遞歸問題

我試圖用karatsuba技術實現大數乘法。我陷入了我無法解決的seg故障。該程序似乎總是在3或4級遞歸後退出。 sizeof（bint）返回20000.我的bint由一組短褲組成。karatsuba乘法，遞歸問題

friend bint operator+ (const bint& lhs, const bint& rhs) 
{ 
    // adding two big integers 
} 

bint ksuba(const bint& X, const bint& Y, int n) // n is always a power of 2 
{ 
    if (n == 4) 
     return smul(X, Y); // naive way of multiplying numbers 

    bint a1, b1, a2, b2; 
    bint x, y, z; 

    int half = n/2; 

    for (int i=0; i<half; i++) 
    { 
     a1.data[SIZE - n + i + half] = X.data[SIZE - n + i]; 
     a2.data[SIZE - n + i + half] = X.data[SIZE - n + i + half]; 

     b1.data[SIZE - n + i + half] = Y.data[SIZE - n + i]; 
     b2.data[SIZE - n + i + half] = Y.data[SIZE - n + i + half]; 
    } 

    a1.idx = SIZE - half; 
    b1.idx = SIZE - half; 
    a2.idx = SIZE - half; 
    b2.idx = SIZE - half; 

    x = ksuba(a1, b1, half); 
    y = ksuba(a2, b2, half); 
    z = ksuba((a1+a2), (b1+b2), n) - x - y; 

    x.lshift(n); 
    z.lshift(half); 

    return x + y + z; 
}

用gdb提供了以下錯誤 -

Program received signal SIGSEGV, Segmentation fault. 
0x00000000004018c2 in bint::ksuba (this=<error reading variable: Cannot access memory at address 0x7fffff7ea3a0>, X=<error reading variable: Cannot access memory at address 0x7fffff7ea398>, Y=<error reading variable: Cannot access memory at address 0x7fffff7ea390>, n=<error reading variable: Cannot access memory at address 0x7fffff7ea38c>) at big.cpp:593 
593     bint ksuba(const bint& X, const bint& Y, int n)

我試圖減少賓特變量我申報的數量。具體來說，我通過將ksuba（a2，b2，half）的結果添加到x本身來擺脫y。但這並不能解決問題。有什麼方法可以知道在遞歸的每一步中分配了多少內存？任何幫助將非常感激。

來源

2012-06-02 shashydhar

爲每個ksuba調用在堆棧上分配的內存量可估計爲7 * sizeof（bint）。你應該用'ulimit'增加堆棧大小，但更好的是，儘可能使用更小的數組。 –

在每個級別上，您有7個顯式聲明的bint類型變量，另外還有2個隱式分配給ksuba（（a1 + a2），（b1 + b2），n）的調用。所有這些都進入堆棧。這是180 KB。如果程序是在調試模式下構建的，沒有進行優化，堆棧使用可能會更大。

180 KB似乎不足以解釋崩潰，因爲（假設這是Linux），默認情況下應該有8 MB的堆棧，並且在3或4次迭代之後不應該耗盡。但是，正如Dmitri提到的那樣，您可以嘗試使用ulimit工具增加堆棧大小，或者在鏈接時通過Wl指定它， - stack = xxxxx選項。更好的是，不要把bint放在堆棧上。用new/delete動態分配它們，只在棧上保留指針。

來源

2012-06-02 05:14:15 user434507

karatsuba乘法，遞歸問題

回答

相關問題