How Did Python Implement the Built-In Function Pow()

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

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.

Python's POW implementation much faster than my own

The builtin is implemented in C which is much faster than implementing it in Python.
It's also probably had several people making speed improvements to it.

What is the difference between Python's built-in `pow` function and the `**` operator?

I found one use for the pow function over the ** operator. First, ** is really raise to a power and apply an optional modulus, as in a**b % c. But if you include the %, its value can't be None. 2**3 % None is an error. pow is really pow(x, y, z=None).

So, if I want to raise a derived value to a power, I could use the operator

>>> def powerizer(db, index, modulus=None):
...     x, y = db.get(index)
...     return x**y % modulus
... 
>>> db = {"foo":[9,3]}
>>> powerizer(db, "foo", 10)
9

But it fails on the default None modulus.

>>> powerizer(db, "foo")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in powerizer
TypeError: unsupported operand type(s) for %: 'int' and 'NoneType'

pow function to the rescue

>>> def powerizer(db, index, modulus=None):
...     x, y = db.get(index)
...     return pow(x, y, modulus)
... 
>>> powerizer(db, "foo", 10)
9
>>> powerizer(db, "foo")
729

Difference between the built-in pow() and math.pow() for floats, in Python?

Quick Check

From the signatures, we can tell that they are different:

pow(x, y[, z])

math.pow(x, y)

Also, trying it in the shell will give you a quick idea:

>>> pow is math.pow
False

Testing the differences

Another way to understand the differences in behaviour between the two functions is to test for them:

import math
import traceback
import sys

inf = float("inf")
NaN = float("nan")

vals = [inf, NaN, 0.0, 1.0, 2.2, -1.0, -0.0, -2.2, -inf, 1, 0, 2]

tests = set([])

for vala in vals:
  for valb in vals:
    tests.add( (vala, valb) )
    tests.add( (valb, vala) )

for a,b in tests:
  print("math.pow(%f,%f)"%(a,b) )
  try:
    print("    %f "%math.pow(a,b))
  except:
    traceback.print_exc()
  
  print("__builtins__.pow(%f,%f)"%(a,b) )
  try:
    print("    %f "%__builtins__.pow(a,b))
  except:
    traceback.print_exc()

We can then notice some subtle differences. For example:

math.pow(0.000000,-2.200000)
    ValueError: math domain error

__builtins__.pow(0.000000,-2.200000)
    ZeroDivisionError: 0.0 cannot be raised to a negative power

There are other differences, and the test list above is not complete (no long numbers, no complex, etc...), but this will give us a pragmatic list of how the two functions behave differently. I would also recommend extending the above test to check for the type that each function returns. You could probably write something similar that creates a report of the differences between the two functions.

math.pow()

math.pow() handles its arguments very differently from the builtin ** or pow(). This comes at the cost of flexibility. Having a look at the source, we can see that the arguments to math.pow() are cast directly to doubles:

static PyObject *
math_pow(PyObject *self, PyObject *args)
{
    PyObject *ox, *oy;
    double r, x, y;
    int odd_y;

    if (! PyArg_UnpackTuple(args, "pow", 2, 2, &ox, &oy))
        return NULL;
    x = PyFloat_AsDouble(ox);
    y = PyFloat_AsDouble(oy);
/*...*/

The checks are then carried out against the doubles for validity, and then the result is passed to the underlying C math library.

builtin pow()

The built-in pow() (same as the ** operator) on the other hand behaves very differently, it actually uses the Objects's own implementation of the ** operator, which can be overridden by the end user if need be by replacing a number's __pow__(), __rpow__() or __ipow__(), method.

For built-in types, it is instructive to study the difference between the power function implemented for two numeric types, for example, floats, long and complex.

Overriding the default behaviour

Emulating numeric types is described here. essentially, if you are creating a new type for numbers with uncertainty, what you will have to do is provide the __pow__(), __rpow__() and possibly __ipow__() methods for your type. This will allow your numbers to be used with the operator:

class Uncertain:
  def __init__(self, x, delta=0):
    self.delta = delta
    self.x = x
  def __pow__(self, other):
    return Uncertain(
      self.x**other.x, 
      Uncertain._propagate_power(self, other)
    )
  @staticmethod
  def _propagate_power(A, B):
    return math.sqrt(
      ((B.x*(A.x**(B.x-1)))**2)*A.delta*A.delta +
      (((A.x**B.x)*math.log(B.x))**2)*B.delta*B.delta
    )

In order to override math.pow() you will have to monkey patch it to support your new type:

def new_pow(a,b):
    _a = Uncertain(a)
    _b = Uncertain(b)
    return _a ** _b

math.pow = new_pow

Note that for this to work you'll have to wrangle the Uncertain class to cope with an Uncertain instance as an input to __init__()

Difference between Python built-in pow and math pow for large integers

math.pow() always returns a floating-point number, so you are limited by the precision of float (almost always an IEEE 754 double precision number). The built-in pow() on the other hand will use Python's arbitrary precision integer arithmetic when called with integer arguments.

---

Related Topics