问题描述
我必须编写一个程序来计算 a**b % c 其中 b 和 c 都是非常大的数字.如果我只是使用a**b % c，它真的很慢.然后我发现内置函数 pow() 可以通过调用 pow(a, b, c) 非常快地做到这一点.
我很想知道 Python 是如何实现的?或者哪里可以找到实现这个功能的源代码文件?
I have to write a program to calculate a**b % c where b and c are both very large numbers. If I just use a**b % c, it's really slow. Then I found that the built-in function pow() can do this really fast by calling pow(a, b, c).
I'm curious to know how does Python implement this? Or where could I find the source code file that implement this function?
推荐答案
如果 a、b 和 c 是整数，则实现可以通过 二元求幂 并在每个步骤中减少模 c 来提高效率，包括第一个(即在开始之前减少 a 模 c ).这就是 确实如此.该函数有两百多行代码，因为它必须处理引用计数、负指数和一大堆特殊情况.
If a, b and c are integers, the implementation can be made more efficient by binary exponentiation and reducing modulo c in each step, including the first one (i.e. reducing a modulo c before you even start). This is what the implementation of long_pow() does indeed. The function has over two hundred lines of code, as it has to deal with reference counting, and it handles negative exponents and a whole bunch of special cases.
不过，该算法的核心思想相当简单.假设我们要为正整数 a 和 b 计算 a ** b，并且 b 具有二进制数字 b_i.那么我们可以把b写成
At its core, the idea of the algorithm is rather simple, though. Let's say we want to compute a ** b for positive integers a and b, and b has the binary digits b_i. Then we can write b as
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的二进制位数.
Each factor in this product is of the form (a**2**i)**b_i. If b_i is zero, we can simply omit the factor. If b_i is 1, the factor is equal to a**2**i, and these powers can be computed for all i by repeatedly squaring a. Overall, we need to square and multiply k times, where k is the number of binary digits of b.
如上所述，对于pow(a, b, c)，我们可以在每一步中减少模c，无论是在平方之后还是在乘法之后.
As mentioned above, for pow(a, b, c) we can reduce modulo c in each step, both after squaring and after multiplying.
这篇关于Python 是如何实现内置函数 pow() 的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！