1

初学者在这里。我大部分时间都在研究 Karatsuba 算法，只是因为我认为它会很有成效。我在这里看到过类似的问题，但它们是用其他语言编写的，而且看起来异常复杂。以下是我的代码。当它遇到对 ac 的递归调用时，它就一直在递归。就好像它从未达到基本情况一样。如果有人能提供一些关于哪里出了问题的见解，将不胜感激。对于此代码，您应该假设我乘以 2、base-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))
4

2 回答 2

3

只需使用整数除法修复代码即可使其正常工作，但这里使用 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
于 2016-10-08T03:57:39.113 回答
1

你想要整数除法吗？在这种情况下，您应该使用：

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

和

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

否则，您的程序将通过小数输入您的函数，我认为这不是故意的。

我也是初学者，欢迎指正。

于 2016-10-08T03:07:29.830 回答