CODEWITHSUNDEEP
pythonalgorithmmathpow
wong2
wong2

Reputation: 35760

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

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?

Upvotes: 65

Views: 45786

Answers (6)

Sven Marnach
Sven Marnach

Reputation: 602775

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. The function has over two hundred lines of code, as it has to deal with reference counting, and it handles negative exponents and a whole bunch of special cases.

At its core, the idea of the algorithm is rather simple, though. Let's say we want to compute a ** b for positive integers a and b, and b has the binary digits b_i. Then we can write b as

b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k

ans a ** b as

a ** b = a**b0 * (a**2)**b1 * (a**2**2)**b2 * ... * (a**2**k)**b_k

Each factor in this product is of the form (a**2**i)**b_i. If b_i is zero, we can simply omit the factor. If b_i is 1, the factor is equal to a**2**i, and these powers can be computed for all i by repeatedly squaring a. Overall, we need to square and multiply k times, where k is the number of binary digits of b.

As mentioned above, for pow(a, b, c) we can reduce modulo c in each step, both after squaring and after multiplying.

Upvotes: 50

RookRaven
RookRaven

Reputation: 523

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

Upvotes: -1

cmaynard
cmaynard

Reputation: 2860

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

Upvotes: -1

Noctis Skytower
Noctis Skytower

Reputation: 22041

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

Upvotes: 40

Jonno_FTW
Jonno_FTW

Reputation: 8809

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.

Upvotes: 0

Andrew Wilkinson
Andrew Wilkinson

Reputation: 10846

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.

Upvotes: -1

Related Questions