问题描述
我必须编写一个程序来计算a**b % c ，其中b和c都是非常大的数字。
如果我只使用a**b % c ，它真的很慢。
然后我发现内置函数pow()通过调用pow(a, b, c)可以非常快地完成此操作。
我很想知道 Python 是如何实现的？
或者在哪里可以找到实现此功能的源代码文件？
1楼
如果a ， b和c是整数，该实现可以由通过更高效的和减少模c在每个步骤中，包括第一个（即减少a模c你甚至开始之前）。
这就是实现确实所做的。
该函数有两百多行代码，因为它必须处理引用计数、负指数和一大堆特殊情况。
不过，该算法的核心思想相当简单。
假设我们要为正整数a和b计算a ** b b ，并且b具有二进制数字b_i 。
那么我们可以把b写成
b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k
ans a ** b as
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 ，并且这些功率可以被计算为所有i通过重复平方a 。
总的来说，我们需要平方和乘以k次，其中k是b的二进制位数。
如上所述，对于pow(a, b, c)我们可以在平方和乘法之后的每一步中减少模c 。
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;
}
3楼
我不知道 python，但如果你需要快速的权力，你可以通过平方使用幂运算：
这是一个简单的递归方法，它使用指数的交换特性。
4楼
在 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
查看此以获取解释
5楼
Python 使用 C 数学库来处理一般情况，并使用它自己的逻辑来处理它的一些概念（例如无穷大）。
6楼
第 1426 行显示了实现 math.pow 的 Python 代码，但基本上归结为它调用标准 C 库，该库可能具有该函数的高度优化版本。
对于密集的数字运算，Python 可能会很慢，但是可以为您提供相当大的速度提升，尽管它不如调用标准库的 C 代码好。