快速加电/连续平方算法在位数较大时移动太慢

Question

所以，我试图用Python实现一个模块化的算术快速供电算法，但是我似乎遇到了严重的瓶颈。 所以，根据我的理解，你应该找到指数的二进制表示，然后计算以^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，因为2的幂次最终得到了真正的 当你碰到20位数字时，会变大，使指数变慢，达到次快的供电速度。 在这个实现中，我是否缺少了模块化算法的一些独特之处？或者我把操作放在不好的地方进行优化？在

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

由于递归，它确实有一点开销，尽管它非常清晰而且仍然相当快。在

或者，如果我想快点：

^{pr2}$