公司做网站的费用如何记账,东莞网站设计推荐易维达2,免费申请电子邮箱,哪个小说网站版权做的好处看了大神讲解#xff0c;理论在这里#xff1a;快速幂算法#xff08;全网最详细地带你从零开始一步一步优化#xff09;-CSDN博客
例题#xff1a;求整数 base 的 整数 power 次方#xff0c;对整数 num_mod 取幂。
python 代码如下#xff1a;
import timedef norm…看了大神讲解理论在这里快速幂算法全网最详细地带你从零开始一步一步优化-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 的案例了。
