看了大神讲解，理论在这里：快速幂算法（全网最详细地带你从零开始一步一步优化）
例题：求整数 base 的 整数 power 次方，对整数 num_mod 取幂。
python 代码如下：
import time
def normalPower(base, power, num_mod):
res = 1
for i in range(int(power)):
res = res * base % num_mod
return res
def fastPower(base, power, num_mod):
res = 1
while power > 0:
if power & 1: # 优化掉： power % 2 == 1
res = res * base % num_mod
power >>= 1 # 优化掉： power = power // 2
# base = (base * base) % num_mod
temp_base = base % num_mod
base = temp_base * temp_base % num_mod
return res
if __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 的案例了。