时间戳

首页 > 解决方案 > 为什么此代码在 karatsuba 乘法中返回负答案

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

问题描述

    """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不应该有任何溢出问题。那么为什么当输入很大时它会返回负答案？

标签： pythonkaratsuba

解决方案

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

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

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

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

推荐阅读