带递归的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

空字符串正以数字的形式传递。前导零会导致字符串的不正确分割。

我相信你最初的，主要的问题是把两个输入从左边分裂成不同的基。他们应该被从右派分裂出来。否则，对他们做数学是没有意义的。你也包括数字的符号在基计算中！

我也相信你的潜入逻辑是脆弱的。它适用于从一个大得多的数字中减去一个小数字，但否则，您可能会在一个已经是负数的数字上连接一个"-“，得到int()无法处理的”-4“这样的结果。

最后，我相信你的数学上有错误。计算但从不使用的值(例如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))