python - Karatsuba 无限递归 - Python

Question

这里是初学者。我花了一天的大部分时间研究 Karatsuba 算法，只是因为我认为它会富有成果。我在这里看到过类似的问题，但它们是用其他语言写的，而且看起来异常复杂。以下是我的代码。一旦它遇到对 ac 的递归调用，它就会继续递归。就好像它从未达到基本情况一样。如果有人能提供一些关于哪里出了问题的见解，我们将不胜感激。对于这段代码，您应该假设我乘以 2、以 10 为基数的四位数。

def karatsuba(x, y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return (x * y)

    else:
        n = (max(len(str(x)), len(str(y))))

        a = x / 10**(n / 2)
        b = x % 10**(n / 2)
        c = y / 10**(n / 2)
        d = y % 10**(n / 2)

        ac = karatsuba(a, c)
        ad = karatsuba(a, d)
        bc = karatsuba(b, c)
        bd = karatsuba(b, d)

        product = (10**n*(ac) + 10**(n/2)*(ad + bc) + bd)

        return product

print (karatsuba(1234, 5678))

Answer 1

只需用整数除法修复您的代码即可使其正常工作，但这里有一个使用 3 个递归调用(以 10 为基数)的略有不同的版本:

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y))) // 2
    p = 10**n

    a, b = divmod(x, p)
    c, d = divmod(y, p)

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d) - ac - bd

    return (ac*p + abcd)*p + bd

但它在二进制和使用位旋转中运行要快得多:

def karatsuba(x, y):
    if x < 16 or y < 16:
        return x * y

    n = max(x.bit_length(), y.bit_length()) // 2
    mask = (1 << n) - 1

    a, b = x >> n, x & mask
    c, d = y >> n, y & mask

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d) - ac - bd

    return (((ac << n) + abcd) << n) + bd