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

回答

相关问题