Python是如何实现内建函数pow()的？

Question

我需要编写一个计算 a**b % c 的程序，其中 b 和 c 都是非常大的数字。如果我使用 a**b % c，速度非常慢。然后我发现内置函数 pow() 可以通过调用 pow(a, b, c) 来快速完成这个计算。
我很好奇 Python 是如何实现这个函数的？或者在哪里可以找到实现这个函数的源代码文件？

- wong2

---

cpython的源代码库位于http://hg.python.org/cpython/。 - Wooble

在_Objects/longobject.c:long_pow()_下（正如JimB已经评论的那样）。 - smci

Answer 1

如果a、b和c都是整数，那么可以通过二进制指数幂算法和在每一步中对模数c进行取模操作（包括第一步，即在开始之前对a取模c），使实现更加高效。这正是long_pow()的实现方式之一。该函数有超过两百行的代码，因为它需要处理引用计数并处理负指数和很多特殊情况。

但基本思想是相当简单的。假设我们要计算正整数a和b的幂a ** b，且b的二进制位为b_i。那么我们可以将b表示成

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

将 a ** b 的结果赋值给 ans

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

每个因子的形式都是 (a**2**i)**b_i。如果b_i为0，我们可以简单地省略这个因子。如果b_i为1，则该因子等于a**2**i，并且这些幂可以通过重复平方a来计算所有i的值。总体而言，我们需要进行k次平方和乘法操作，其中k是二进制数字b的位数。

如上所述，对于pow(a, b, c)，我们可以在每一步中将其模c约减，包括平方和乘法之后。

- Sven Marnach

---

为什么我们可以在每一步中通过模数c来减少？ - Ben Sandler

因为 a ≡ a' (mod c) 和 b ≡ b' (mod c) 意味着 ab ≡ a'b' (mod c)，或者换句话说，无论是先将 a 和 b 对 c 取模再相乘，还是先相乘再对 c 取模都没有关系。详见模运算的维基百科页面。 - Sven Marnach

请注意，long_pow现在在该文件的另一行中定义：https://github.com/python/cpython/blob/master/Objects/longobject.c#L4246 - JohanC

@JohanC 我已更新链接，包括提交哈希，以便它不再过时。 - Sven Marnach

Answer 2

以下两种实现方法可以快速计算(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;
}

- Noctis Skytower

---

@Noctis，我尝试运行你的Python实现，但出现了以下错误：TypeError: ufunc 'bitwise_and'不支持输入类型，并且根据强制转换规则“safe”，输入无法安全地强制转换为任何受支持的类型。----由于我正在学习Python，所以我想你可能对这个错误有些想法（搜索表明它可能是一个bug，但我认为有一个快速解决方法）。 - stackuser

@stackuser：在以下演示中，它似乎正常工作：http://ideone.com/sYzqZN - Noctis Skytower

有人能解释一下为什么这个解决方案可行吗？我很难理解这个算法背后的逻辑。 - kilojoules

@NoctisSkytower，考虑到本地的Python pow()内置函数也支持此功能并且似乎更快，这样做的好处是什么？ `>>> st_pow ='pow(65537L, 767587L, 14971787L)'

st_pow_mod = 'pow_mod(65537L, 767587L, 14971787L)' timeit.timeit(st_pow) 4.510787010192871 timeit.timeit(st_pow_mod, def_pow_mod) 10.135776996612549`

- Fabiano

@Fabiano 我的函数不应该被使用。它简单地解释了 Python 如何在幕后工作，而不涉及其 C 源代码。我试图回答 wong2 的问题，他想知道 pow 是如何实现的。 - Noctis Skytower

Answer 3

我不了解Python，但如果你需要快速求幂，可以使用平方取幂算法：

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

这是一个简单的递归方法，利用指数的交换律。

- Jonno_FTW

Answer 4

Python在一般情况下使用C数学库，而对于一些概念（如无穷大）则使用自己的逻辑。

- cmaynard

Answer 5

這個文件的第1426行顯示了實現math.pow的Python代碼，但基本上它歸結為調用標准C庫，該庫可能具有高度優化的版本。

對於大量數字運算而言，Python可能會很慢，但Psyco可以為您提供相當大的速度提升，儘管它不如調用標準庫的C代碼好。

- Andrew Wilkinson

---

math.pow()函数没有取模参数，也不是与内置函数pow()相同的函数。另外，提醒一下，Psyco已经过时了，也不支持64位。对于严肃的数学计算，NumPy非常好用。 - JimB

Answer 6

在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

看看这个链接的解释

- Akshay Nair

Answer 7

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

我有一个包含12个相当大的质数的列表，跨越了9154个ASCII字节，每个十进制数字占用1个字节（已经排除了\n），并且组合成1320个组合。

 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 ⤴ | python 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秒。

- RARE Kpop Manifesto

---

请不要滥用反引号来强调。它们不适用于产品名称或其他你认为重要的随机事物。它们仅适用于内联代码和文件名。 - undefined

@Chris：当然可以。你能否现在解释一下我发现的为什么会有如此荒谬的差异？当差异达到一个数量级时，这确实有点令人担忧。 - undefined

不是当它被发布为答案而不是问题时。你在这里已经待了足够长的时间，应该知道网站的运作方式，但如果你需要复习一下，可以随时回顾一下[导览]。 - undefined

@Chris: 系统不让我发问题，我该怎么办？ - undefined

我是一个普通用户，不是版主。我对你的账户和发帖历史了解得比你少得多（尤其是可能已被删除的内容）。你可能想从这里开始。 - undefined