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

Question

我必须编写一个程序来计算a**b % c哪里b和c都是非常大的数字.如果我只是使用a**b % c它,它真的很慢.然后我发现内置函数pow()可以通过调用来快速完成pow(a, b, c).
我很想知道Python是如何实现这一点的？或者我在哪里可以找到实现此功能的源代码文件？

Answer 1

如果a,b和c都是整数,实现可以进行通过更高效的二进制幂和减少模c中的每一步,包括第一次(即降低a模c,你甚至开始之前).这是实施的long_pow()确实.

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