0

我正在尝试在 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))
4

1 回答 1

0

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

a: 1
b: 02
c: 
d: 2

空字符串作为数字传递。前导零会导致字符串的不正确拆分。

我相信您最初的主要问题是将两个输入从左侧按不同的基数拆分。它们应该从右边被同一个基数分开。否则，对它们进行数学运算毫无意义。您还将数字的符号包括在基本计算中！

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

最后，我相信你的数学有错误。您计算但从不使用的值（例如ad和bc）使情况更加复杂。

下面是我在解释Wikipedia 中的 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))
于 2022-01-03T01:38:20.780 回答