编写 Karatsuba 乘法代码时在 Python 中遇到递归错误

Question

我是算法新手，我正在尝试使用递归函数调用为 Karatsuba 乘法算法编写代码。

我知道 karatsuba 乘法通过像这样将它们分成两半来处理偶数 n 位数字，其中 2 个数字是 10^n/2 * a + b 和 10^n/2 * c + d 一个b Xcd

乘积是通过计算10^n * ac + 10^n/2 * [(a+b)(c+d) - ac - bd] + b*d

这是我的代码，带有注释解释。

    def multiplication_algorithm(num1, num2):
        length1 = len(str(num1))
        length2 = len(str(num2))
        length = max(length1, length2)
        if length == 1:
            return num1 * num2 #simply returns product if single digit inputs are encountered
        num1_str = str(num1)
        num2_str = str(num2)
        num1_str = '0' * (length - length1) + num1_str #makes the length of both strings the same by adding zeros to the beginning
        num2_str = '0' * (length - length2) + num2_str
        if length % 2 != 0:
            num1_str = "0" + num1_str #makes the length of strings even so they can be symmetrically split
            num2_str = "0" + num2_str
        mid = length//2
        num1_first_half = int(num1_str[:mid]) #next 4 lines break the 2 numbers in 4 halves
        num1_second_half = int(num1_str[mid:])
        num2_first_half = int(num2_str[:mid])
        num2_second_half = int(num2_str[mid:])
        part1 = multiplication_algorithm(num1_first_half, num2_first_half)
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
        part2 = multiplication_algorithm(num1_first_half + num1_second_half, num2_first_half + num2_second_half) - part1 - part3
        return (10 ** length) * part1 + (10 ** mid) * part2 + part3

    import random
    s=set()
    for i in range(10): #generating 10 pairs of random numbers in given range to check algorithm
        number1 = random.randint(1,999)
        number2 = random.randint(1,99)
        if multiplication_algorithm(number1, number2) == number1 * number2:
            print("Success")
        else:
            print("Failure")

当我运行使用 random.randint(1,99) 计算 number1 和 number2 的这段代码时，这段代码运行完美，但是当我运行使用 number1=random.randint(1,99) 和 number2=random.randint(1,999) 如上，代码失败并产生递归深度错误。我已将错误文本复制粘贴到此处：

    Traceback (most recent call last):
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 29, in <module>
        if multiplication_algorithm(number1, number2) == number1 * number2:
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      [Previous line repeated 1018 more times]
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 19, in multiplication_algorithm
        part1 = multiplication_algorithm(num1_first_half, num2_first_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 4, in multiplication_algorithm
        length = max(length1, length2)
    RecursionError: maximum recursion depth exceeded in comparison

递归次数远远超过应有的次数，我不明白代码中发生的位置。

Answer 1

至少有一个问题与 4 位数字有关。您将它们分成两个 two-digit 个数字。 num1_first_half + num2_second 可能会给出一个 3 位数的数字，然后在开头添加一个 0，使您回到四位数。

维基百科页面建议在长度=4 时停止递归。

Answer 2

将字符串扩展为偶数长度后，使用旧长度计算 mid。

if length % 2 != 0:
    num1_str = "0" + num1_str
    num2_str = "0" + num2_str
    length += 1    # <-- this was missing

mid = length//2

编写 Karatsuba 乘法代码时在 Python 中遇到递归错误

Recursion Error encountered in Python while writing code for Karatsuba multiplication

python

algorithm

recursion

multiplication