Karatsuba乘法与递归

Question

我正在尝试用Python实现Karatsuba乘法。不幸的是，我的代码在64位测试用例(我正在研究的课程(中失败了，因为我的高斯计算开始产生负数。我在下面包含了我的代码，想知道是否有人能为我提供一些指导。

此外，我有意将这些大数字存储为字符串，因为这项任务的全部目的是挑战自己调用递归。我相信Python能够自动处理这些大数字，但它将击败这项任务中具有挑战性的部分。

输入都是64位数字。

def karatsuba(input1, input2):
    first_number = len(input1)
    second_number = len(input2)
    # base case
    if first_number <= 2:
        return str(int(input1) * int(input2))
    else:
        # first half
        # changing the divider from round(first_number/2) to first_number // 2 yielded different results.
        if first_number % 2 == 1:
            add_zero = first_number + 1
        else:
            add_zero = first_number
        divider_a = first_number // 2
        a = input1[:divider_a]
        b = input1[divider_a:]
        print("a: " + a)
        print("b: " + b)
        # second half
        divider_b = second_number // 2
        c = input2[:divider_b]
        d = input2[divider_b:]
        print("c: " + c)
        print("d: " + d)
    # recursive
    ac = karatsuba(a, c)
    print("ac: " + ac)
    bd = karatsuba(b, d)
    print("bd: " + bd)
    ad = karatsuba(a, d)
    print("ad: " + ad)
    bc = karatsuba(b, c)
    print("bc: " + bc)
    # for subtraction, you add the negative.
    def addition(input_a, input_b):
        return str(int(input_a) + int(input_b))
    ab_cd = karatsuba(addition(a, b), addition(c, d))
    print("ab_cd: " + ab_cd)
    gauss = addition(addition(ab_cd, "-"+ac), "-"+bd)
    print("gauss: " + gauss)
    merge1 = ac + "0"*add_zero
    print("merge1: " + merge1)
    merge2 = gauss + str(("0"*(add_zero//2)))
    print("merge2: " + merge2)
    merge3 = bd
    return (addition(addition(merge1, merge2), merge3))
if __name__ == '__main__':
    input_a, input_b = map(str, input().split())
    print(karatsuba(input_a, input_b))

Answer 1

当我测试代码时，它会出现一个ValueError: invalid literal for int() with base 10: ''错误。您可以在调试输出中看到一个问题：

a: 1
b: 02
c: 
d: 2

空字符串被当作数字传递。并且前导零会导致字符串的错误拆分。

我相信你最初的主要问题是用左的不同基来划分两个输入。它们应该由相同的基数从右侧分割。否则，对它们进行数学运算毫无意义。您还将数字的符号包含在基本计算中！

我也相信你的减法逻辑是脆弱的。它的作用是从一个大得多的数字中减去一个小数字，但除此之外，您会面临连接一个"的风险-"在已经为负数的数字上--4〃；CCD_ 2无法处理。

最后，我相信你的数学有错误。由于您计算但从未使用过的值(例如ad和bc(，它变得更加复杂。

以下是我根据维基百科中Karatsuba算法的解释对您的代码进行的返工，我在他们的例子和一对随机的64位数字上进行了测试。它仍然有缺陷，例如，数字符号仍然可以影响基数计算，减法仍然很脆弱，等等。但基本上证明了算法：

def karatsuba(input1, input2):
    print("input1: {}, input2: {}".format(input1, input2))
    length1 = len(input1)
    length2 = len(input2)
    # base case
    if length1 <= 2 or length2 <= 2:
        return str(int(input1) * int(input2))
    # first half
    base_length = min(length1, length2) // 2
    divider_a = length1 - base_length
    high1, low1 = input1[:divider_a], input1[divider_a:]
    while len(low1) > 1 and low1[0] == '0':
        low1 = low1[1:]  # remove leading zeros
    print("high1:", high1, "low1:", low1)
    # second half
    divider_b = length2 - base_length
    high2, low2 = input2[:divider_b], input2[divider_b:]
    while len(low2) > 1 and low2[0] == '0':
        low2 = low2[1:]  # remove leading zeros
    print("high2:", high2, "low2:", low2)
    # recursive
    z0 = karatsuba(low1, low2)
    print("z0:", z0)
    z2 = karatsuba(high1, high2)
    print("z2:", z2)
    def addition(input_a, input_b):
        return str(int(input_a) + int(input_b))
    # The four multiplication Babbage solution:
    #
    # z1 = addition(karatsuba(low1, high2), karatsuba(high1, low2))
    # print("z1:", z1)
    # The three multiplication Gauss solution:
    # This approach may cause overflow, see https://en.wikipedia.org/wiki/Karatsuba_algorithm for a work around
    # For subtraction, you add the negative.
    z1 = addition(addition(karatsuba(addition(high1, low1), addition(high2, low2)), f"-{z2}"), f"-{z0}")
    print("z1: ", z1)
    return addition(addition(z2 + "0" * (base_length * 2), z1 + "0" * (base_length * 1)), z0 + "0" * (base_length * 0))
if __name__ == '__main__':
    a = "7392297780844983031173686285210463614020982285096612188770501341"
    b = "4688026175884269750785003351250107609139231296129030834139247897"
    print(karatsuba(a, b))