Karatsuba算法太多的递归 [英] Karatsuba algorithm too much recursion

问题描述

我正在尝试在c ++中实现Karatsuba乘法算法，但现在我只是想使其在python中工作.

I am trying to implement the Karatsuba multiplication algorithm in c++ but right now I am just trying to get it to work in 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函数是否递归正确?如果是这样，我就在某个地方搞砸了，因为递归没有停止.

What I don't get is: how should z2, z1, and z0 be created? Is using the mult function recursively correct? If so, I'm messing up somewhere because the recursion isn't stopping.

有人可以指出错误在哪里吗?

Can someone point out where the error is?

推荐答案

注意:以下回复直接解决了OP关于以下问题的问题: 过多的递归，但它不会尝试提供正确的 Karatsuba算法.其他答复在以下方面提供的信息要多得多 这方面.

NB: the response below addresses directly the OP's question about excessive recursion, but it does not attempt to provide a correct Karatsuba algorithm. The other responses are far more informative in this regard.

尝试此版本:

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和y1为0，则算法的推导不成立，因为在这种情况下，分解步骤变得无效.因此，必须通过确保x和y都大于b ** m来避免这种可能性.

The most serious problem with your version is that your calculations of x0 and x1, and of y0 and y1 are flipped. Also, the algorithm's derivation does not hold if x1 and y1 are 0, because in this case, a factorization step becomes invalid. Therefore, you must avoid this possibility by ensuring that both x and y are greater than b**m.

修复了代码中的错字；补充说明

fixed a typo in the code; added clarifications

为清楚起见，请直接评论原始版本:

To be clearer, commenting directly on your original version:

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

这篇关于Karatsuba算法太多的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！