Karasuba算法递归过多

我正在尝试用 c++ 实现 Karasuba 乘法算法，但现在我只是想让它在 python 中工作。

这是我的代码：

def mult(x, y, b, m):
    if max(x, y) < b:
        return x * y

    bm = pow(b, m)
    x0 = x / bm
    x1 = x % bm
    y0 = y / bm
    y1 = y % bm

    z2 = mult(x1, y1, b, m)
    z0 = mult(x0, y0, b, m)
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0

    return mult(z2, bm ** 2, b, m) + mult(z1, bm, b, m) + z0

我不明白的是：应该如何z2, z1, and z0被创造？正在使用mult函数递归正确吗？如果是这样，我就在某个地方搞砸了，因为递归没有停止。

有人能指出错误在哪里吗？

注意：下面的回复直接解决了OP的问题 过度递归，但它并没有尝试提供正确的 唐叶算法。其他回复的信息量要大得多 对此。

试试这个版本：

def mult(x, y, b, m):
    bm = pow(b, m)

    if min(x, y) <= bm:
        return x * y

    # NOTE the following 4 lines
    x0 = x % bm
    x1 = x / bm
    y0 = y % bm
    y1 = y / bm

    z0 = mult(x0, y0, b, m)
    z2 = mult(x1, y1, b, m)
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0

    retval = mult(mult(z2, bm, b, m) + z1, bm, b, m) + z0
    assert retval == x * y, "%d * %d == %d != %d" % (x, y, x * y, retval)
    return retval

您的版本最严重的问题是 x0 和 x1 以及 y0 和 y1 的计算被翻转。此外，该算法的推导不成立，如果x1 and y1是 0，因为在这种情况下，因式分解步骤变得无效。因此，您必须通过确保 x 和 y 都大于 b**m 来避免这种可能性。

编辑：修复了代码中的拼写错误；补充说明

EDIT2:

为了更清楚，直接评论你的原始版本：

def mult(x, y, b, m):
    # The termination condition will never be true when the recursive 
    # call is either
    #    mult(z2, bm ** 2, b, m)
    # or mult(z1, bm, b, m)
    #
    # Since every recursive call leads to one of the above, you have an
    # infinite recursion condition.
    if max(x, y) < b:
        return x * y

    bm = pow(b, m)

    # Even without the recursion problem, the next four lines are wrong
    x0 = x / bm  # RHS should be x % bm
    x1 = x % bm  # RHS should be x / bm
    y0 = y / bm  # RHS should be y % bm
    y1 = y % bm  # RHS should be y / bm

    z2 = mult(x1, y1, b, m)
    z0 = mult(x0, y0, b, m)
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0

    return mult(z2, bm ** 2, b, m) + mult(z1, bm, b, m) + z0