看了大神讲解，理论在这里：快速幂算法（全网最详细地带你从零开始一步一步优化）-CSDN博客

例题：求整数 base 的 整数 power 次方，对整数 num_mod 取幂。

python 代码如下：

import timedef normalPower(base, power, num_mod):res = 1for i in range(int(power)):res = res * base % num_modreturn resdef fastPower(base, power, num_mod):res = 1while power > 0:if power & 1:  # 优化掉： power % 2 == 1res = res * base % num_modpower >>= 1  # 优化掉： power = power // 2# base = (base * base) % num_modtemp_base = base % num_modbase = temp_base * temp_base % num_modreturn resif __name__ == '__main__':time1 = time.time()print(fastPower(2, int(1e8), 1000))print("fastPower Time:", round((time.time() - time1) * 1000, 5), 'ms')time2 = time.time()print(normalPower(2, int(1e8), 1000))print("normalPower Time:", round((time.time() - time2) * 1000, 5), 'ms')

输出如下： 

我们再把数字设大一点：

print(fastPower(int(1e200), int(1e100), 1000))

耗时依旧是 0.0ms。

我们分析一下：

1、首先是矩阵快速幂，相比传统的方法，提速效果直接到毫秒级别。

2、“位运算”优化掉除以2的运算
power >>= 1  # 优化掉： power = power // 2

3、“与运算”优化掉偶数判断
if power & 1:  # 优化掉： power % 2 == 1

4、这里是我个人做的优化，考虑到 base 的值可能很大的情况

        # 下面两行优化掉 base = (base * base) % num_mod
        temp_base = base % num_mod
        base = temp_base * temp_base % num_mod

整体优化过后，基本上找不到超过 0.0ms 的案例了。