自己实现的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

问题出在拆分上。您需要以 low（右）部分的大小为 n 的方式拆分。这是必要的，因为 x 和 y 的 high 部分必须是可比较的：它们必须是通过除以 10.

的 same 次方提取

所以把拆分代码改成这样：

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

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

自己实现的Karatsuba算法

Own implementation of Karatsuba algorithm

python

algorithm

multiplication

karatsuba