所谓快速幂是指快速求得a的b次方的方法.求a^b,最朴素的想法便是不断进行b次累乘,但真的需要进行b次乘法运算吗?
假如要计算2^32,当求得2^16次方之后,可以直接对2^16进行平方得到2^32,并不需要在2^16基础上再进行16次累乘.
相应地,求2^16只需对2^8求平方即可.同理,求2^8,只需对2^4平方......以此类推.
那么1,4,8,16是怎么算出来的呢?
29的二进制表示为11101
所以$29=2^4+2^3+2^2+2^0=16+8+4+1 $
这样就确定了3的哪些次幂是要进行累乘的.
作者签名:简单地活着 肆意又精彩.