karatsuba算法在Python

所以我實現在Python Karatsuba的乘算法。現在我有無限遞歸，無法解決它。有任何想法嗎？如果需要，我會提供更多的代碼。karatsuba算法在Python

def multiply(self, other): 


    # helper function 
    def split(largeInt, n): 
    least = largeInt._least_significant_digits(n/2) 
    most = largeInt._right_shift(n/2) 
    if debug: assert least.to_int() + (most.to_int() << (LargeInt.base_bits*(n/2))) == largeInt.to_int() 
    return least, most 
    n = max(len(str(self)),len(str(other))) 
    if (n==1): 
    return self.to_int() * other.to_int() 
    else: 
    aR, aL = split(self,n) 
    bR , bL = split(other, n) 
    x1 = aL.multiply(bL) 
    x2 =aR.multiply(bR) 
    a = aL.add(bL) 
    b = aR.add(bR) 
    x3=a.multiply(b) 
    # code for recursive step here 
    #return 1 # change this line with your implementation 
    return x1 * 10**n + (x3-x1-x2) * 10**(n/2) + x2

來源

2012-05-01 Marty Griffin

的代碼有像「TODO：你在這裏實施」的意見和「代碼基本情況在這裏」在裏面。它在實際的Karatsuba代碼之前也有'return 2'。你在這裏發佈了正確的代碼嗎？ –

此代碼需要正確縮進。 – deebee

我看到你已經在代碼中放置了一些診斷打印語句。他們展示了什麼？一旦深入到無限遞歸中，什麼值被傳遞給'multiply'？你確定你調用的大整數方法做你想要的嗎？是'n/2'產生一個整數還是浮點數，如果後者不好？ –

我正在計算被傳入的數字的最大長度，這樣做固定它。

n = max(len(self.digits),len(other.digits))

來源

2012-05-01 15:04:54

一些提示：

我不認爲你值a，b，是what you want them to be。
一個常見的錯誤往往是分不返回嚴格較小的數字：請爲_least_significant_digits提供源，_right_shift。
當你輸入一個是長度爲1的，而不是其他的什麼情況？在這種情況下，1位數字的分割返回是什麼？

來源

2012-05-01 09:42:21 huitseeker

karatsuba算法在Python

回答

相關問題