0

我正在尝试在 Python 上实现 Karatsuba 乘法。输入是长度为 2 的两个整数。它们的长度相同。

def mult(x,y):
    if int(x) < 10 and int(y) <10:
        return int(x)*int(y)
    x_length = len(str(x))//2
    y_length = len(str(y))//2

    a = str(x)[:x_length]
    b = str(x)[x_length:]
    c = str(y)[:y_length]
    d = str(y)[y_length:]

    n = len(a) + len(b)
    m = n//2

    return 10**n* mult(a,c) + 10**m*(mult(a+b, c+d)-mult(a,c)-mult(b,d)) + mult(b,d)

运行 mult(1234,5678) 这会产生以下错误：

if int(x) < 10 and int(y) <10:
RecursionError: maximum recursion depth exceeded while calling a Python object

但是，如果我这样做

def mult(x,y):
    if int(x) < 10 and int(y) <10:
        return int(x)*int(y)
    x_length = len(str(x))//2
    y_length = len(str(y))//2

    a = str(x)[:x_length]
    b = str(x)[x_length:]
    c = str(y)[:y_length]
    d = str(y)[y_length:]

    n = len(a) + len(b)
    m = n//2

    return 10**n* mult(a,c) + 10**m*(mult(a,d)+mult(b,c)) + mult(b,d)

所以我在最后一行（即mult(a,c), mult(a,d), mult(b,c), mult(b,d)）中进行了 4 次递归，而不是上面的 3 次（即mult(a,c), mult(a+b, c+d), mult(b,d)）。

然后事实证明没问题。

为什么会这样？我怎么能只用 3 次递归呢？

4

2 回答 2

1

a, b, c, d是字符串。字符串加法是连接。"1" + "2"是"12"。所以传递给mult(a+b, c+d)的不是你打算传递的。

TL;博士。

首先，递归应该很快终止。让我们看看为什么没有。print x, y在开头添加mult：

def mult(x, y):
    print x, y
    ....

并将输出重定向到文件中。结果令人惊讶：

1234 5678
12 56
1 5
12 56
1 5
12 56
1 5
12 56
1 5
....

难怪堆栈溢出。问题是，为什么我们要重复这个12 56案例？让我们添加更多工具，找出哪个递归调用做到了：

def mult(x,y,k=-1):
    ....
    print a, b, c, d
    ac = mult(a, c, 0)
    bd = mult(b, d, 2)
    return 10**n* ac + 10**m*(mult(a+b, c+d, 1) - ac - bd) + bd

结果是

-1 :  1234 5678
12 34 56 78
0 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56

可以看到标记为1always的递归调用12 56。计算的是调用mult(a + b, c + d)。那好吧。它们a, b, c, d都是字符串。"1" + "2"是"12"。不完全是你的意思。

所以，下定决心：参数是整数还是字符串，并相应地对待它们。

于 2019-08-21T21:00:32.923 回答
0

请注意，在您的第一个代码片段中 - 您不是三次调用您的函数，而是 5 次：

return 10**n* mult(a,c) + 10**m*(mult(a+b, c+d)-mult(a,c)-mult(b,d)) + mult(b,d)

对于您的其余代码，我真的不能说，但是快速浏览一下 Karatsuba 上的 Wikipedia 条目，您可以通过增加您使用的基数（即从 10 到 100 或 1000）来减少递归深度。您可以使用更改递归深度，sys.setrecursionlimit但 python 堆栈帧可能会变得非常大，因此请尽量避免这样做，因为它可能很危险。

于 2019-08-21T05:31:04.597 回答