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

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

I don't know about python, but if you need fast powers, you can use exponentiation by squaring:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

It's a simple recursive method that uses the commutative property of exponents.

Line 1426 of this file shows the Python code that implements math.pow, but basically it boils down to it calling the standard C library which probably has a highly optimized version of that function.

Python can be quite slow for intensive number-crunching, but Psyco can give you a quite speed boost, it won't be as good as C code calling the standard library though.

Python uses C math libraries for general cases and its own logic for some of its concepts (such as infinity).

Implement pow(x,n) in Python

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

Implement pow(x,n,m) in Python

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

Checkout this link for explanation