Python 是如何实现内置函数 pow（） 的？

Python 将 C 数学库用于一般情况，并将自己的逻辑用于某些概念（例如无穷大）。

该文件的第 1426 行显示了实现 math.pow 的 Python 代码，但基本上它归结为它调用标准 C 库，该库可能具有该函数的高度优化版本。

Python 对于密集的数字运算来说可能很慢，但 Psyco 可以给你带来相当大的速度提升，但它不如调用标准库的 C 代码好。

我不了解python，但如果你需要快速的幂，你可以通过平方来使用幂：

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

这是一种简单的递归方法，它使用指数的交换特性。

如果 和 是整数，则可以通过二进制幂和每个步骤中的约简模来提高实现效率，包括第一步（即在开始之前约简模）。这就是 long_pow（） 的实现所做的。该函数有两百多行代码，因为它必须处理引用计数，并且它处理负指数和一大堆特殊情况。abccac

不过，从本质上讲，该算法的想法相当简单。假设我们要计算正整数 和 ，并且有二进制数字。然后我们可以写成a ** babbb_ib

b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k

ans 作为a ** b

a ** b = a**b0 * (a**2)**b1 * (a**2**2)**b2 * ... * (a**2**k)**b_k

本产品中的每个因素都是 的形式。如果为零，我们可以简单地省略该因子。如果为 1，则因数等于 ，并且可以通过重复平方来计算所有这些幂。总的来说，我们需要平方和乘以乘法，其中 是 的二进制位数。(a**2**i)**b_ib_ib_ia**2**iiakkb

如上所述，我们可以在每一步中减少模，无论是在平方之后还是在乘法之后。pow(a, b, c)c

您可以考虑以下两种实现来快速计算。(x ** y) % z

在 Python 中：

def pow_mod(x, y, z):
    "Calculate (x ** y) % z efficiently."
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

在 C 语言中：

#include <stdio.h>

unsigned long pow_mod(unsigned short x, unsigned long y, unsigned short z)
{
    unsigned long number = 1;
    while (y)
    {
        if (y & 1)
            number = number * x % z;
        y >>= 1;
        x = (unsigned long)x * x % z;
    }
    return number;
}

int main()
{
    printf("%d\n", pow_mod(63437, 3935969939, 20628));
    return 0;
}

在 Python 中实现 pow（x，n）

def myPow(x, n):
        p = 1
        if n<0:
            x = 1/x
            n = abs(n)

        # Exponentiation by Squaring

        while n:
            if n%2:
                p*= x
            x*=x
            n//=2
        return p

在 Python 中实现 pow（x，n，m）

def myPow(x,n,m):
            p = 1
            if n<0:
                x = 1/x
                n = abs(n)
            while n:
                if n%2:
                    p*= x%m
                x*=x%m
                n//=2
            return p

查看此链接以获取说明

只想添加一个关于Python 3.11.6内置的数据点：pow(-mod-)

我列出了 12 个相当大的素数，跨越大约 9,154 个 ASCII 字节，每个十进制数字 1 个字节（已经排除了 s），并组成了 1,320 种组合\n

 a ** b % c   =>  pow(a, b, c) 

---

 python3 -c 'import sys
 
 sys.set_int_max_str_digits(8**9 - 1)

 [ print(__.strip(), str(pow(int((_ := __.split())[0]),
                             int(_[1]),
                             int(_[2])))) for __ in sys.stdin ]' 

并以 GNU GMP（过度 gawk）为基准，我用一个准系统拍了拍：powmod()

function powmod(__, ___, ____, _,
          _____, ______, _______) {
    
    if (_ = !+____)
        return "NAN_POWMOD_ZERO"

    ___ %= (____ += _++) - (_____ = \
            (__  %= ____)^(______ = !++_))

    while (_+_ <= ___)
        ___%_ && (___ = --___/_) || ______ * (___ /= _) \
      ? \
        (_____ = _____*__%____) < (__ = __*__%____) \
                                :  __ = __*__%____
    return \
        ___<_ ? _____*__ % ____ : \
        _<___ ?     __*__ % ____*__*_____%____ : \
               __*_____*__ % ____
}

通过散列确认它们的输出是相同的。

   out9:  112KiB 0:00:00 [ 468KiB/s] [ 347KiB/s] [<=> ]
 lines9:   1.32k 0:00:10 [ 121 /s] [ <=> ]
   out9: 3.85MiB 0:00:10 [ 362KiB/s] [ 362KiB/s] [ <=> ]
 
  ( echo "${aaaaaaaaaaaaaaaaaaa}" | mawk 'NF = / is prime$/' | mawk2  FS='\n' |)  

 10.79s user 0.07s system 99% cpu 10.873 total

 1  2eed768a72e116b4b50afa74afc53067  stdin

---

gmp-via-awk ⤴ （英语） |蟒蛇 3.11.6 ⤵

---

 lines9:   1.32k 0:02:27 [8.95 /s] [<=> ]
   out9: 3.85MiB 0:02:27 [26.7KiB/s] [26.7KiB/s] [  <=> ]

 ( echo "${aaaaaaaaaaaaaaaaaaa}" | mawk 'NF = / is prime$/' | mawk2  FS='\n' |)

 146.46s user 0.74s system 99% cpu 2:27.55 total

 1  2eed768a72e116b4b50afa74afc53067  stdin

由于我不清楚的原因，Python 3 在其他地方花费了不到 11 秒的时间完成一项任务，大约需要 2 分 27 秒。我第二次运行它，它仍然是 10.6 秒，而不是 2 分 24.7 秒。