Karatsuba无限递归- Python

Question

新手。我花了一天的大部分时间研究Karatsuba算法，因为我认为它会很有成效。我在这里看到过类似的问题，但它们是用其他语言写的，看起来奇怪地复杂。以下是我的代码。当它碰到对ac的递归调用时，它就会继续递归。就好像它永远不会碰到基本情况一样。如果有人能好心地就问题出在哪里提供一些见解，我将不胜感激。对于这段代码，您应该假设我是将以10为基数的2个四位数相乘。

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

Answer 2

要整数除法吗?在这种情况下，您应该使用:

a = x // 10 ** (n / 2)

和

c = y // 10 ** (n / 2)

否则，你的程序将通过小数传递给你的函数，我认为这是无意的。

我也是一个初学者，请随时纠正我