前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >快速幂算法

快速幂算法

作者头像
渔父歌
发布2020-06-22 15:47:11
4990
发布2020-06-22 15:47:11
举报
文章被收录于专栏:数据结构笔记

求解一个数的 n次方,我们一般直接累乘 n次,就像下面的代码一样:

代码语言:javascript
复制
def pow(x, n):
    result = 1
    for i in range(n):
        result *= x
    return result

但是这种方法只能用于指数 n比较小的情况,如果指数 n非常大的话,这种方法就不再适用了。

遇到这种情况下快速幂算法能够很好的解决我们的需求。

递归实现

观察 x^10 = x^5 * x^5 而 x^5 = x^4 * x 而 x^4 = x^2 * x^2 而 x^2 = x * x 即:x->x2->x5->x^10 根据上面的观察我们可以发现,下一步的结果总是上一步的平方或者上一步的平方再乘 x。

这样我们可以按照下面的规则从右边向左边计算:

  1. 计算 x^[n/2]。
  2. 如果 n是偶数,直接返回,否则乘上 x再返回。
  3. 如果 n=1,返回 x。

我们可以用递归来实现这个算法:

代码语言:javascript
复制
import math

def pow(x, n):
    if n == 1:
        return x
    
    r = pow(x, math.floor(n/2))
    return r*r if n%2 == 0 else r*r*x

迭代实现

任意一个正整数都可以用二进制来表示,比如:7 = 111(2) = 2^2 + 2^1 + 2^0 所以:x^7 = x ^ (2^2 + 2^1 + 2^0) = x^4 * x^2 * x 我们可以发现前一个式子总是后一个式子的 2n次方。

所以我们只要计算 x, x^2, x^4, x^8, ... , x^(2^n) ,然后根据 n的二进制表示来判断对应位是否带入计算,如果第 n位为 1,则结果乘上 x^(2^n),然后计算 x^(2^(n+1)),否则只计算 x^(2^(n+1))。

代码如下:

代码语言:javascript
复制
def pow(x, n):
    target = x
    result = 1
    while n > 0:
        if (n & 1) == 1:
            result *= target
        n = n >> 1
        target *= target
    return result

如果考虑 n为负数的情况,只需要在前面添加判断即可。 如果 n为负数,则 x = 1/x, n=-n。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 递归实现
  • 迭代实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档