python pow函数的底层实现原理介绍

一、最朴素的方法和pow比较

python中求两个a的b次方，常见的方法有:pow(a,b),a**b。那么这两个是否有区别，而且他们底层是怎么实现的呢？

最容易想到的方法就是：循环b次，每次都乘以a。但是究竟底层是不是这样实现的呢？

下面先从时间上来判断他们之间的关系。

首先来看看，pow和**有没有区别：

import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)

上面的结果输出如下：

2的100万次方，两者所用时间是基本一样的，所以他们应该本质上应该使用了相同的算法

下面再来看看用for循环模拟的结果

import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)
r = 1
for i in range(1000000):
  r *= 2
end2 = time.time()
print('for:', end2 - end1)

上面的输入结果如下:

非常恐怖的对比，pow和**都只用了1.5秒，而for循环用来20秒！，所以可以肯定的是，pow底层绝对不是用循环去求解的

二、pow底层实现

我们分析一下为什么直接循环相乘效率会这么低，我们其实不难发现里面有大量的重复运算，比如我们算出22后面，还不断重复着计算22的结果，所以我们只要保存这些中间必要的计算结果后你不断重复利用就可以大大减少运算量。

举个例子，比如我们现在在计算2的9次方，我们可以这样子计算，先算出22然后不断利用这个结果：（22）（22）（22）（22）2 即44442 只要计算5次

同理可以再利用上面的44 可以的16162

具体实现程序如下：

def fun(a, b):
  r = 1
  while b > 1:
    if b & 1 == 1: #与运算一般可以用于取某位数，这里就是取最后一位。
      r *= a
    a *= a
    b = b >> 1 #这里等价于b//=2
  return r * a

接下我们来看看，究竟pow函数底层是不是这样实现的

import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)
r = 1
for i in range(1000000):
  r *= 2
end2 = time.time()
print('for:', end2 - end1)
print(fun(2, 1000000))
print('fun:', time.time() - end2)

从上面可以看出来，pow函数运行的时间基本和自定义的函数一致，甚至自定制的还更快！

解析完毕！

补充：Python3 的pow函数用法 及效率

Python3自带pow函数：

1. pow（a,b） 表示求a的b次方 a^b

2.pow(a,b,c) 表示求a的b次方取余c a^b%c

然后 用pow函数求出来的 a^b%c 时间上可以与“快速幂取模算法” 相媲美！

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。如有错误或未考虑完全的地方，望不吝赐教。

赞 (0)

相关推荐

  • pow在python中的含义及用法

    pow()方法返回xy(x的y次方) 的值 语法 以下是math模块pow()方法的语法: import math math.pow( x, y ) 内置的pow()方法 pow(x, y[, z]) 函数是计算x的y次方,如果z在存在,则再对结果进行取模,其结果等效于pow(x,y) %z 注意:pow() 通过内置的方法直接调用,内置方法会把参数作为整型,而 math 模块则会把参数转换为 float. 参数 x -- 数值表达式.y -- 数值表达式.z -- 数值表达式. 返回值 返回

  • Python输出PowerPoint（ppt）文件中全部文字信息的方法

    本文实例讲述了Python输出PowerPoint(ppt)文件中全部文字信息的方法.分享给大家供大家参考.具体分析如下: 下面的代码依赖于windows com,所以必须在机器上安装PowerPoint才能用,可以将PPT文件中的所有纯文本信息进行输出到指定的文件,非常实用. import win32com from win32com.client import Dispatch, constants ppt = win32com.client.Dispatch('PowerPoint.App

  • Python中pow()和math.pow()函数用法示例

    本文实例讲述了Python中pow()和math.pow()函数用法.分享给大家供大家参考,具体如下: 1. 内置函数pow() >>> help(pow) Help on built-in function pow in module __builtin__: pow(...) pow(x, y[, z]) -> number With two arguments, equivalent to x**y. With three arguments, equivalent to (

  • Python numpy.power()函数使用说明

    power(x, y) 函数,计算 x 的 y 次方. 示例: x 和 y 为单个数字: import numpy as np print(np.power(2, 3)) 8 分析:2 的 3 次方. x 为列表,y 为单个数字: print(np.power([2,3,4], 3)) [ 8 27 64] 分析:分别求 2, 3, 4 的 3 次方. x 为单个数字,y 为列表: print(np.power(2, [2,3,4])) [ 4 8 16] 分析:分别求 2的 2, 3, 4 次

  • PowerBI和Python关于数据分析的对比

    PowerBI和Python关于数据分析的对比

    前言 如果你对数据分析有一定的了解,那你一定听说过一些亲民好用的数据分析的工具,如Excel.Tableau.PowerBI等等等等,它们都是数据分析的得力助手.像经常使用这些根据的伙伴肯定也有苦恼的时候,不足之处也是显而易见:操作繁琐,复用性差,功能相对局限单一. 很多经常会用到数据分析的伙伴会问有没有一款便捷好用的工具!肯定有啊,Python的出现和普及,很容易就能改变这些窘境! 怎么解决呢?--Python Python有很多优点,如果你能很好的运用到工作中,会发现工作效率大大提升,涨薪也

  • python中pow函数用法及功能说明

    幂运算是高更数学的应用学科,是一种关于幂的数学运算.同底数幂相乘,底数不变,指数相加.同底数幂相除,底数不变,指数相减.幂的乘方,底数不变,指数相乘.适用于精确计算领域. 计算机作为精确计算的一种方式,含有大量的幂运算.在python中就有内置函数pow函数表示幂的运算. 1.pow()函数 Python的内置函数,它计算并返回x的y次方的值. 2.语法 pow(x, y, z) 3.参数 x -- 数值表达式. y -- 数值表达式. z -- 数值表达式. 4.返回值 返回 x y (x的y

  • python通过ssh-powershell监控windows的方法

    本文实例讲述了python通过ssh-powershell监控windows的方法.分享给大家供大家参考.具体分析如下: 对于服务器的监控来说,监控linux不管是自己动手写脚本还是用一些开源的工具比如nagios,zenoss什么的.但毕竟还是有些公司有windows做服务器的,相对linux来说,windows没有方便的shell,cmd下提供的命令对于监控来说远远没有linux方便.但是现在windows上如果安装了powershell(win7,2008自带),就比以前方便多了,linu

  • python pow函数的底层实现原理介绍

    python pow函数的底层实现原理介绍

    一.最朴素的方法和pow比较 python中求两个a的b次方,常见的方法有:pow(a,b),a**b.那么这两个是否有区别,而且他们底层是怎么实现的呢? 最容易想到的方法就是:循环b次,每次都乘以a.但是究竟底层是不是这样实现的呢? 下面先从时间上来判断他们之间的关系. 首先来看看,pow和**有没有区别: import time start = time.time() print(2 ** 1000000) end0 = time.time() print('**:', end0 - sta

  • Python 列表(List)的底层实现原理分析

    Python 列表的数据结构是怎么样的? 列表实际上采用的就是数据结构中的顺序表,而且是一种采用分离式技术实现的动态顺序表 但这是不是Python的列表? 我的结论是顺序表是列表的一种实现方式. 书上说的是:列表实现可以是数组和链表. 顺序表是怎么回事?顺序表一般是数组. 列表是一个线性的集合,它允许用户在任何位置插入.删除.访问和替换元素. 列表实现是基于数组或基于链表结构的.当使用列表迭代器的时候,双链表结构比单链表结构更快. 有序的列表是元素总是按照升序或者降序排列的元素. 实现细节 py

  • Python的函数使用示例详解

    Python的函数使用示例详解

    目录 1 跳出循环-break 2 python函数 2.1 内置函数 2.2 自定义函数 2.3 main函数 在两种python循环语句的使用中,不仅仅是循环条件达到才能跳出循环体.所以,在对python函数进行阐述之前,先对跳出循环的简单语句块进行介绍. 1 跳出循环-break python提供了一种方便快捷的跳出循环的方法-break,示例如下,计算未知数字个数的总和: if __name__ == "__main__": sum = 0 while True: num =

  • Python排序函数的使用方法详解

    Python排序函数完美体现了Python语言的简洁性,对于List对象,我们可以直接调用sort()函数(这里称为"方法"更合适)来进行排序,而对于其他可迭代对象(如set,dict),我们可以使用更灵活的sorted()函数. 一.List的sort()函数 Python源码builtins.py文件对sort()函数的定义如下 def sort(self, key=None, reverse=False): """ L.sort(key=None,

  • 10个有用的Python字符串函数小结

    目录 前言 一.capitalize() 函数 二.lower( ) 函数 三.title( ) 函数 四.casefold() 函数 五.upper( ) 函数 六.count( ) 函数 七.find( ) 函数 八.replace() 函数 九.swapcase( ) 函数 十.join () 函数 前言 Python 字符串是一个内置的类型序列.字符串可用于处理 Python 中的文本数据.Python 字符串是 Unicode 点的不可变序列.在 Python 中创建字符串是最简单易用

  •  Python 匿名函数lambda 详情

    目录 1.前言 2.如何使用 lambda 3.总结 1.前言 在 Python 中,说到函数,大家都很容易想到用 ​​def​​ 关键字来声明一个函数: def Hello():     # function body 然后我们可以在​添加由圆括号括起来的参数列表.函数体内可能有很多行代码,里面有尽可能多的语句和表达式.​ 除了 ​​def​​​ 语句定义函数以外,还有一种生成函数对象的表达式形式: ​​lambda​​ 表达式,这个表达式创建了一个能够随时调用的函数. 有时声明一个函数只有一

  • 如何利用Python拟合函数曲线详解

    如何利用Python拟合函数曲线详解

    目录 拟合多项式 函数说明 拟合任意函数 函数说明 总结 使用Python拟合函数曲线需要用到一些第三方库: numpy:科学计算的基础库(例如:矩阵) matplotlib:绘图库 scipy:科学计算库 如果没有安装过这些库,需要在命令行中输入下列代码进行安装: pip install numpy matplotlib scipy 拟合多项式 ''' Author: CloudSir Date: 2021-08-01 13:40:50 LastEditTime: 2021-08-02 09:

  • Python的函数使用介绍

    Python的函数使用介绍

    目录 1 跳出循环-break 2 python函数 2.1 内置函数 2.2 自定义函数 2.3 main函数 1 跳出循环-break python提供了一种方便快捷的跳出循环的方法-break, 示例如下,计算未知数字个数的总和: if __name__ == "__main__": sum = 0 while True: num = str(input('输入的数字 (或者 "完成"): ')) if num == '完成': break #跳出循环 sum

  • python set()去重的底层原理及实例

    python set()去重的底层原理及实例

    目录 set是什么? set特点 一.set去重简单实例 二.重新set实现机制 三.结论 四.应用场景需求 set是什么? 数学上,把set称做由不同的元素组成的集合,集合(set)的成员通常被称做集合元素(set elements).Python把这个概念引入到它的集合类型对象里.集合对象是一组无序排列的可哈希的值.集合关系测试和union.intersection等操作符在Python里也同样如我们所预想地那样工作. set特点 集合的元素有三个特征: 1.确定性:集合中的元素必须是确定的

  • python中的函数递归和迭代原理解析

    python中的函数递归和迭代原理解析

    这篇文章主要介绍了python中的函数递归和迭代原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.递归 1.递归的介绍 什么是递归? 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大

随机推荐