如何快速算出一个数的n次方？
投稿作者 OIer，目前对计算机及算法的了解主要在信息学竞赛方面。
本文主要讲解平方求幂（快速幂）相关，凡涉及大整数，都会进行对定值取模等处理，所以存储越界导致的错误、位数过多导致的单次运算缓慢的问题，不在考虑范围之内。
我们仍然以
为例，考虑一下
可以表示成什么。
这样我们就可以写出一份递归的伪代码：
function power(a, n):
if n = 0 then return 1
t := power(a, (n - n mod 2) / 2)
if n mod 2 = 1
then: return t^2 * a
else: return t^2
每次将数据规模缩小为原来的一半，这种方法的时空复杂度是
。
a
这样，我们由低位向高位计算，每次将底数平方即可。
下面两份伪代码，分别对应这种方法的如上两种实现。
function power(a, n):
pow[0...log n], pow[0] := 1
for i: 1 to inf
if (2^i > n) break
else pow[i] = pow[i - 1]^2
res := 1
for i: 1 to inf
if (2^i > n) break
else:
if (n bitand 2^i) res = res * pow[i]
return res
# n bitand 2^i 可理解为 n 在二进制表示下含 2^i 位
function power(a, n):
res := 1, p := a
while n > 0:
if (n bitand 1) then res = res * a
p = p^2, n = n >> 1
return res
# bitand 表示按二进制位与，>> 表示按二进制位右移（可理解为除以 2 下取整）。
这样的时间复杂度仍为
，空间复杂度为
。
这种方法，就是平方求幂，也叫快速幂。
在一些其他的地方，也会用到这种思想。
比如：求
要知道，绝大部分语言中，能存储的最大整数都只是
。如果我们直接计算，可能会自然溢出造成答案错误。
这时，我们就想到平方求幂的思想。
我们考虑
于是我们考虑通过
求出
。即：
function times(a, b, m):
if b = 0 then return 0
t := times(a, (b - b mod 2) / 2, m)
if b mod 2 = 1
then: return ((t + t) mod m + a mod m) mod m
else: return (t + t) mod m
同样地，也可以对 进行二进制拆分。
function power(a, b, m):
res := 0
while b > 0:
if (b bitand 1) then res = (res + a) mod m
a = (a + a) mod m, b = b >> 1
return res
# bitand 表示按二进制位与，>> 表示按二进制位右移（可理解为除以 2 下取整）。
这样，我们用
的时间复杂度算出了大数乘积取模的值。俗称“龟速乘”。
事实上，平方求幂的思想，在任何具有结合律的、参与运算的数据相同的运算中，都可以使用。
如矩阵乘法等。
好了，快速求幂的方法就讲到这里，如果对你有哦帮助，欢迎点赞哦~~
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-07-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
