How did Python implement the built-in function pow()?


Question

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?

1
45
3/9/2011 2:07:38 PM

Accepted Answer

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.

38
11/28/2018 1:35:33 AM

You might consider the following two implementations for computing (x ** y) % z quickly.

In 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

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

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon