python - Karatsuba算法的自己实现

Question

大家好，我正在尝试提出自己的 Karatsuba 乘法算法实现，其中当一个数字是单个数字时，基本情况是微不足道的乘法。我的代码似乎无法产生正确的答案，我相信这与 z1 的计算方式有关，但我不太明白，请帮帮我。

import math
x = input()
y = input()

def suba(x,y):
    if len(x) == 1 or len(y) == 1:
        x = int(x)
        y = int(y)
        return x*y
    else:
        n = int(math.ceil((min(len(x),len(y)))/2))
        h1 = x[0:n]
        l1 = x[n:len(x)]
        h2 = y[0:n]
        l2 = y[n:len(y)]
        z0 = suba(l1,l2)
        z1 = suba(str(int(l1)+int(h1)),str(int(l2)+int(h2)))
        z2 = suba(h1,h2)
        return (z2*10**(n*2))+((z1-z2-z0)*10**(n))+z0

print(suba(x,y))

Answer 1

问题在于分裂。您需要以这样的方式拆分低（右）部分的大小为n。这是必要的，因为x和y的高部分必须是可比较的：它们必须是通过除以 10 的相同幂来提取的。

所以将拆分代码更改为：

    h1 = x[:-n]
    l1 = x[-n:]
    h2 = y[:-n]
    l2 = y[-n:]

另请注意，不必为范围的开头指定 0，也不必为范围的结尾指定长度，因为这些是默认值。