在kartsuba算法中，没有得到任何结果，而是陷入了无限循环

Question

我没有得到任何结果，我的程序陷入了无限循环我用相同的逻辑为四个值制作了一个程序，效果很好，但有三个值，就不起作用了

def Karatsuba_Recursive(a, b):
if not a or not b:
return "0"
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
else:
m = max(len(a),len(b))
m2 = m // 2
A = a[0:-m2]
B = a[-m2:len(a)].lstrip("0")
C = b[0:-m2]
D = b[-m2:len(b)].lstrip("0")
val1 = int(Karatsuba_Recursive(A,C))
val2 = int(Karatsuba_Recursive(B,D))
val3 = int(Karatsuba_Recursive((str(A+B)),str((C+D))))
return str((val1 * (10 **(2*m2))) + ((val3 - val1 - val2) * (10**(m2))) + val2)

Answer 1

主要问题是A+B是字符串串联，而不是数字加法。这应该是int(A)+int(B)。与C+D相同。

不幸的是，您选择m作为max(len(a),len(b))，因为这使得有必要进行第一次if not a or not b测试，并且您还需要调整上述修复程序以使用空字符串。

你可以用min(len(a),len(b))代替m来避免这一切。