如何快速算出一个数的n次方？

比眉伴天荒 2022-08-30 11:25 144阅读 0赞

投稿作者 OIer，目前对计算机及算法的了解主要在信息学竞赛方面。

本文主要讲解平方求幂（快速幂）相关，凡涉及大整数，都会进行对定值取模等处理，所以存储越界导致的错误、位数过多导致的单次运算缓慢的问题，不在考虑范围之内。

--------------------

“幂”在许多地方常被用到，如 Hash 相关、费马小定理、进制转换等。

一般来说，我们要求，只需要将乘次即可，时间复杂度为。

但有时，极大，这种方法需要的时间开销是不可接受的。

比如，求。

如果我们直接计算多个这样的式子，至少在目前主流计算机中，所用时间以分钟计。

我们考虑如何优化对的计算。

--------------------

以计算为例。

我们发现，，所以我们可以先计算出，再计算。

于是我们想到一种方法：先计算，

再计算。

这样，我们就可以通过把分解为约个大小为的块，将时间复杂度由降为。

事实上，如果递归下去，这个做法可以做到，但常数较大，经测试速度约为下面两种做法的。

--------------------

我们仍然以为例，考虑一下可以表示成什么。

![e264490f2c35c48a721d91281dd397c5.png][]

我们考虑，于是我们考虑通过的值求出。设，有：

这样我们就可以写出一份递归的**伪**代码：

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

每次将数据规模缩小为原来的一半，这种方法的时空复杂度是。

--------------------

接下来仍然以计算为例，假设你什么也不知道，只会由小向大计算，那么：

第一次乘法，只能计算。

第二次，考虑得到尽量大的值，于是计算得。

第三次，进一步，。

我们发现，第次可以得到。

。

……

第次，

第次，。

先计算存储下来再求值，不失为一种好方法；但亦可以在计算的同时判断分解为的幂（即转为进制）后是否含，边计算边乘。

形式化地，对于位，其代表的幂为（）。

这样，我们由低位向高位计算，每次将底数平方即可。

下面两份伪代码，分别对应这种方法的如上两种实现。

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 下取整）。

这样，我们用的时间复杂度算出了大数乘积取模的值。俗称“龟速乘”。

--------------------

事实上，平方求幂的思想，在任何具有结合律的、参与运算的数据相同的运算中，都可以使用。

如矩阵乘法等。

好了，快速求幂的方法就讲到这里，如果对你有哦帮助，欢迎点赞哦~~

[e264490f2c35c48a721d91281dd397c5.png]: /images/20220829/5055eb1307e8419db8d05299050079af.png