投稿作者OIer，目前对计算机及算法的了解主要在信息学竞赛方面。
本文主要讲解平方求幂（快速幂）相关，凡涉及大整数，都会进行对定值取模等处理，所以存储越界导致的错误、位数过多导致的单次运算缓慢的问题，不在考虑范围之内。
“幂”在许多地方常被用到，如Hash相关、费马小定理、进制转换等。
一般来说，我们要求
，只需要将
乘
次即可，时间复杂度为
。
但有时，
极大，这种方法需要的时间开销是不可接受的。
比如，求
。
如果我们直接计算多个这样的式子，至少在目前主流计算机中，所用时间以分钟计。
我们考虑如何优化对
的计算。
以计算
为例。
我们发现，
，所以我们可以先计算出
，再计算
。
于是我们想到一种方法：先计算
，
再计算
。
这样，我们就可以通过把
分解为约
个大小为
的块，将时间复杂度由
降为
。
事实上，如果递归下去，这个做法可以做到
，但常数较大，经测试速度约为下面两种做法的
。
我们仍然以
为例，考虑一下
可以表示成什么。
我们考虑
，于是我们考虑通过
的值求出
。设
，有：
这样我们就可以写出一份递归的伪代码：
functionpower(a,n):ifn=0thenreturn1t:=power(a,(n-nmod2)/2)ifnmod2=1then:returnt^2*aelse:returnt^2
每次将数据规模缩小为原来的一半，这种方法的时空复杂度是
。
接下来仍然以计算
为例，假设你什么也不知道，只会由小向大计算，那么：
第一次乘法，只能计算
。
第二次，考虑得到尽量大的值，于是计算得
。
第三次，进一步，
。
我们发现，第
次可以得到
。
。
……
第
次，
第
次，。
第
次，
。
第
次，
。
先计算存储下来再求值，不失为一种好方法；但亦可以在计算
的同时判断
分解为
的幂（即转为
进制）后是否含
，边计算边乘。
形式化地，对于
位，其代表的幂
为
（
）。
这样，我们由低位向高位计算，每次将底数平方即可。
下面两份伪代码，分别对应这种方法的如上两种实现。
functionpower(a,n):pow[0...logn],pow[0]:=1fori:1toinfif(2^in)breakelsepow[i]=pow[i-1]^2res:=1fori:1toinfif(2^in)breakelse:if(nbitand2^i)res=res*pow[i]returnres#nbitand2^i可理解为n在二进制表示下含2^i位
functionpower(a,n):res:=1,p:=awhilen0:if(nbitand1)thenres=res*ap=p^2,n=n1returnres#bitand表示按二进制位与，表示按二进制位右移（可理解为除以2下取整）。
这样的时间复杂度仍为
，空间复杂度为
。
这种方法，就是平方求幂，也叫快速幂。
在一些其他的地方，也会用到这种思想。
比如：求
，
。
要知道，绝大部分语言中，能存储的最大整数都只是
。如果我们直接计算，可能会自然溢出造成答案错误。
这时，我们就想到平方求幂的思想。
我们考虑，
，于是我们考虑通过
求出
。即：
functiontimes(a,b,m):ifb=0thenreturn0t:=times(a,(b-bmod2)/2,m)ifbmod2=1then:return((t+t)modm+amodm)modmelse:return(t+t)modm
同样地，也可以对
进行二进制拆分。
functionpower(a,b,m):res:=0whileb0:if(bbitand1)thenres=(res+a)modma=(a+a)modm,b=b1returnres#bitand表示按二进制位与，表示按二进制位右移（可理解为除以2下取整）。
这样，我们用
的时间复杂度算出了大数乘积取模的值。俗称“龟速乘”。
事实上，平方求幂的思想，在任何具有结合律的、参与运算的数据相同的运算中，都可以使用。
如矩阵乘法等。
好了，快速求幂的方法就讲到这里，如果对你有哦帮助，欢迎点赞哦~~
-END-
本文编辑：佚名
转载请注明出地址 http://www.jiubiyinga.com/hxfc/12813.html
