当前位置:首页 > 公众号精选 > 程序员小灰
[导读]投稿作者OIer,目前对计算机及算法的了解主要在信息学竞赛方面。本文主要讲解平方求幂(快速幂)相关,凡涉及大整数,都会进行对定值取模等处理,所以存储越界导致的错误、位数过多导致的单次运算缓慢的问题,不在考虑范围之内。“幂”在许多地方常被用到,如Hash相关、费马小定理、进制转换等...

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

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

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

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

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

比如,求

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

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

以计算 为例。

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

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

再计算

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

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

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

我们考虑 ,于是我们考虑通过 的值求出 。设 ,有:



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

function power(a, n):
 if n = 0 then return 1
 t := power(a, (n - n mod 2) / 2)
 if n mod 2 = 1
 thenreturn t^2 * a
 elsereturn 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
 thenreturn ((t   t) mod m   a mod m) mod m
 elsereturn (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 下取整)。
这样,我们用 的时间复杂度算出了大数乘积取模的值。俗称“龟速乘”。

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

如矩阵乘法等。

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

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
关闭
关闭