python - 为什么此代码在 karatsuba 乘法中返回负答案

Question

    """karatsuba algo"""
def fast(x,y):
    if len(str(x))==1 or len(str(y))==1:
        return x*y
    else:
        n = max(len(str(x)),len(str(y)))
        m = n//2

        a = x//10**m
        b = x%10**m
        c = y//10**m
        d = y%10**m

        k = fast(a,c)
        n = fast((a+b),(c+d))
        o = fast(b,d)

        return (10**2*m*k) +(10**m*(n-k-o))+(o)
print(fast(10515610,5651551460))

python不应该有任何溢出问题。那么为什么当输入很大时它会返回负答案？

Answer 1

查看原始算法，您的代码应该是

return (10**(2*m)*k) +(10**m*(n-k-o))+(o)

查看周围的附加括号(2*m)。否则，您将乘以 m 而不是提高幂。

您可以通过用10**m新变量替换所有位来使其更具可读性和效率

Answer 2

我检查了这个，发现问题不在于 Python 溢出。与or相比，您o在最后一次迭代中的值要大得多。两者都得到值 6 而包含 17487400。因此导致了负面结果。knknon-k-o