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):

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

}

Answer 2

在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