python - 快速供电/连续平方算法移动速度太慢，数字量较大

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

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

或者，如果我希望它更快:

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