我必須編寫一個程序來計算a**b % c在哪里，b并且c都是很大的數字。如果我只是使用a**b % c，那真的很慢。然后，我發現內置函數pow()可以通過調用來真正快速地做到這一點pow(a, b, c)。我很好奇Python是如何實現的？或者在哪里可以找到實現此功能的源代碼文件？
3 回答
大話西游666
TA貢獻1817條經驗 獲得超14個贊
您可以考慮以下兩種實現方式來(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;
}
繁花如伊
TA貢獻2012條經驗 獲得超12個贊
在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
添加回答
舉報
0/150
提交
取消