快速幂运算/连续平方算法在处理大位数时速度过慢

Question

我正在尝试在Python中实现一个模运算的快速幂算法，但似乎遇到了很大的瓶颈。 根据我的理解，你需要找到指数的二进制表示，然后计算基数的平方（base^2^i），其中i是二进制位数。 我的Python代码是网上和教科书上常见的算法定义的实现：

    def fastPower(base, exp, mod):
        base %= mod
        workingExp = exp
        product = 1
        upperBound = range(int(math.ceil(math.log(exp,2))))
        for i in upperBound:
            print upperBound
            binDigit = workingExp % 2
            workingExp /= 2
            binExp = (binDigit << i)
            product *= base ** binExp
            product %= mod
        return product

瓶颈出现在 product *= base ** binExp 这一行，因为当你处理20位数字时，2的幂会变得非常大，这会导致幂运算的速度变得很慢，远远达不到快速幂的效果。 在这个实现中，我是不是遗漏了什么与模运算相关的独特之处？或者说，我是否把某些操作放在了不太合适的位置，影响了优化效果？

Answer 1

嗯……我对这样的东西更熟悉：

def fastPower(base, exp, mod):
    if exp == 0:
        x = 1
    else:
        half = fastPower(base, exp // 2, mod)  # just / in Python 2
        x = half * half
        if exp % 2 == 1:
            x *= base
    return x % mod

虽然因为使用了递归，这种方法会有一点额外的开销，但它的逻辑非常清晰，而且速度也还算快。

或者，如果我想让它更快的话：

def fastPower(base, exp, mod):
    return pow(base, exp, mod)