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

Question

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

Answer 1

我对Python不太了解，但如果你需要快速计算幂，可以使用“平方取幂”这个方法：

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

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

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;
}

Answer 3

如果 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 可以写成

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

这个乘积中的每个因子都是 (a**2**i)**b_i 的形式。如果 b_i 是零，我们可以直接省略这个因子。如果 b_i 是 1，那么这个因子就是 a**2**i，而这些幂可以通过不断地对 a 进行平方来计算。总体来说，我们需要平方和相乘 k 次，其中 k 是 b 的二进制位数。

正如上面提到的，对于 pow(a, b, c)，我们可以在每一步中对 c 取模，无论是平方之后还是相乘之后。