快速幂算法

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

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。

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

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))。

代码如下:

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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 中值滤波

    中值滤波使用当前像素点和它周围的8个像素点的中值来代替当前点额像素点,这个办法对去除椒盐噪声非常有效。

    渔父歌
  • 实战:爬取简书之搭建程序框架

    随机选择 ua,将下面这段代码单独放到一个文件中(user-agent太多了╯︿╰):

    渔父歌
  • 利用简书图片上传功能搭建快速免费的图床

    后来发现简书的写文章页面可以上传图片,于是萌生了利用简书的图片上传功能来搭建一个图床的想法。

    渔父歌
  • 编码篇-iOS开发中的奇巧小伎

    最近搜集了自己以前的笔记中的一些小知识点,归为这篇文章,都是亲测有效的奇巧小伎,当你使用到时,你会大呼过瘾的。

    進无尽
  • 剑指offer【10~19】

    f(n) = f(n-1) + f(n-2) + ... + f(0),其中 f(i) 表示从第 i 层跳到第 n 层的跳法。化简的 f(n) = 2 * f(...

    echobingo
  • 关于安卓下拉刷新时的悬浮菜单栏

    最近在github上遇到一个下拉刷新上拉加载的项目--BGARefreshLayout。地址。使用里面的BGARefreshLayout嵌套一个

    用户4458175
  • iOS SDWebimage 源码阅读

    简介 SDWebimage是 iOS 的图片加载框架。它支持从网络中下载且缓存图片,并设置图片到对应的 UIImageView 控件或者 UIButton 控...

    赵哥窟
  • (六十九)c#Winform自定义控件-垂直滚动条

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • 聊聊sentinel的DegradeSlot

    com/alibaba/csp/sentinel/slots/block/degrade/DegradeSlot.java

    codecraft
  • SpringMVC过滤器、拦截器与监听器的区别

    飞狗

扫码关注云+社区

领取腾讯云代金券