Karatsuba算法过多的递归

Question

我正在尝试用c ++实现Karatsuba乘法算法但是现在我只是想让它在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和z0被创造出来的？使用mult函数递归正确吗？如果是这样,我在某处乱搞,因为递归并没有停止.

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

Answer 1

注意:下面的响应直接解决了OP关于过度递归的问题,但它没有尝试提供正确的Karatsuba算法.其他答复在这方面提供了更多信息.

试试这个版本:

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的计算被翻转.此外,算法的推导不保持if x1和y10,因为在这种情况下,因子分解步骤变为无效.因此,您必须通过确保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