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

Question

我必须编写一个程序来计算a**b % c在哪里，b并且c都是很大的数字。如果我只是使用a**b % c，那真的很慢。然后，我发现内置函数pow()可以通过调用来真正快速地做到这一点pow(a, b, c)。
我很好奇Python是如何实现的？或者在哪里可以找到实现此功能的源代码文件？

Answer 1

您可以考虑以下两种实现方式来(x ** y) % z快速进行计算。在Python中：def pow_mod(x, y, z):&nbsp; &nbsp; "Calculate (x ** y) % z efficiently."&nbsp; &nbsp; number = 1&nbsp; &nbsp; while y:&nbsp; &nbsp; &nbsp; &nbsp; if y & 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; number = number * x % z&nbsp; &nbsp; &nbsp; &nbsp; y >>= 1&nbsp; &nbsp; &nbsp; &nbsp; x = x * x % z&nbsp; &nbsp; return number在C中：#include <stdio.h>unsigned long pow_mod(unsigned short x, unsigned long y, unsigned short z){&nbsp; &nbsp; unsigned long number = 1;&nbsp; &nbsp; while (y)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (y & 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; number = number * x % z;&nbsp; &nbsp; &nbsp; &nbsp; y >>= 1;&nbsp; &nbsp; &nbsp; &nbsp; x = (unsigned long)x * x % z;&nbsp; &nbsp; }&nbsp; &nbsp; return number;}int main(){&nbsp; &nbsp; printf("%d\n", pow_mod(63437, 3935969939, 20628));&nbsp; &nbsp; return 0;}

Answer 2

在Python中实现pow（x，n）def myPow(x, n):&nbsp; &nbsp; &nbsp; &nbsp; p = 1&nbsp; &nbsp; &nbsp; &nbsp; if n<0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = 1/x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n = abs(n)&nbsp; &nbsp; &nbsp; &nbsp; # Exponentiation by Squaring&nbsp; &nbsp; &nbsp; &nbsp; while n:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n%2:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p*= x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x*=x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n//=2&nbsp; &nbsp; &nbsp; &nbsp; return p在Python中实现pow（x，n，m）def myPow(x,n,m):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p = 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n<0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = 1/x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n = abs(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while n:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n%2:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p*= x%m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x*=x%m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n//=2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return p