# Episode 2 Teaser Companion Blog Post: The Magic Behind Integer Arithmetic in Python

Note: This blog post is a companion to our Episode 2 Teaser.

# Exponents in Python: `**`, not `^`

Suppose you want to calculate a large number like 2 to the 38th power. If you've used a Texas Instruments graphing calculators or a mathematical typesetting language like LaTeX, you might instinctively try the following in Python:

``````>>> 2^38
36
``````

After a quick Google search, it's clear the caret (`^`) denotes "bitwise exclusive or", which isn't at all what we wanted. Per Python's documentation, we could instead write the computation in either of the following ways:

``````>>> 2**38
274877906944
>>> pow(2,38)
274877906944
``````

Even though `2**38` and `pow(2,38)` produce the same number, through, one of them is working harder behind the scenes. To see this, consider a simple timing experiment. Using the `timeit` module, we can find the average execution time when each operation is repeated one million times:

``````>>> import timeit
>>> timeit.timeit('2**38', number=1000000)
0.01468262099660933 # this is about one-seventieth of a second
>>> timeit.timeit('pow(2,38)', number=1000000)
0.3849993069889024 # this is about one-third of a second
``````

In other words, `2**38` takes about one-seventieth of a second, while `pow(2,38)` takes more than one-third of a second. That's a big difference!

# Why `2**38` is faster than `pow(2,38)`

To see why `2**38` is faster, we can use the `dis` module to dissemble each operations into bytecode. In other words, we can turn each line of code into its underlying set of fundamental instructions:

``````>>> import dis
>>> dis.dis('2**38')
2 RETURN_VALUE
>>> dis.dis('pow(2,38)')
6 CALL_FUNCTION            2
8 RETURN_VALUE
``````

In particular, `pow(2,38)` disassembled form included the bytecode `CALL_FUNCTION`, while `2**38` does not. Given Python's reputation for having expensive function calls, it seems reasonable for `pow(2,38)` to be an order of magnitude slower than `2**38`.

# Sidenote: `pow != math.pow`

However, not all function calls are created equal, and the number of lines of bytecodes is not necessarily indicative of execution time. To see this, here's yet another method for computing 2 to the 38th power, along with it's disassembled form:

``````>>> import math
>>> math.pow(2,38)
274877906944.0
>>> import timeit
>>> timeit.timeit('import math; math.pow(2,38)', number=1000000)
0.277645947993733 # this is about one-quarter of a second
>>> import dis
>>> dis.dis('import math; math.pow(2,38)')
4 IMPORT_NAME              0 (math)
6 STORE_NAME               0 (math)
16 CALL_FUNCTION            2
18 POP_TOP
22 RETURN_VALUE
``````

Despite having the same name, the built-in function `pow` and the method `math.pow` from the `math` module are quite different. The built-in version performs exact integer-multiplication, allowing arbitrarily large integers to be created (try it -- it's fun!). The version from the `math` module, though, can produce approximate results more quickly using floating-point operations. However, this also means `math.pow` is susceptible to overflow when a non-integer becomes too large for Python to represent:

``````>>> import math; math.pow(2,138)
3.48449143727041e+41
>>> import math; math.pow(2,1038)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: math range error
``````

# The magic behind exponentiation

In case you're not tired of computing `2**38`, we came up with three more methods, and will leave it up to you to provide your own bytecode disassembly for the first two:

``````>>> 1<<38 # compute 2**38 by shifting a bit left 38 times
274877906944
>>> import timeit
>>> timeit.timeit('1<<38', number=1000000)
0.015056486008688807 # this is about one-seventh of a second

>>> import functools
>>> import operator
>>> functools.reduce(operator.mul, *38) # compute 2**38 by explicitly building 2*2*...*2
274877906944
>>> timeit.timeit('import functools; import operator; functools.reduce(operator.mul, *38)', number=1000000)
3.335591795970686 # this is more than three seconds!

>>> (2).__pow__(38) # compute 2**38 using a magic method call
274877906944
>>> timeit.timeit('(2).__pow__(38)', number=1000000)
0.39968948398018256 # this is about one-third of a second
>>> dis.dis('(2).__pow__(38)')
6 CALL_FUNCTION            1
8 RETURN_VALUE
``````

Working our way through these examples,

1. the obtuse bit-shifting trick for computing powers of `2` is the fastest;

2. explicitly building `2` multiplied by itself `38` times is the slowest; and

3. having the integer `2` explicitly call the so-called "magic method" `__pow__` has roughly the same performance and bytecode representation as `pow(2,38)`. (Note that parentheses are necessary around 2. This prevents Python from assuming the period is a decimal point and throwing a SyntaxError. Ask us how we know.)

The notation `(2).__pow__(38)` looks strange, but it's essentially how Python is computing `pow(2,38)` under the hood. Everything in Python is represented as an object, even integers, and all objects can be used to invoke methods from the class they represent. And per the documentation for the operator module, writing `pow(2,38)` is the same as having `2` invoke the class method `__pow__`, and the magic method is what actually produces the value of `2**38`.

In other words, `pow(2,38)` reduces to `(2).__pow__(38)`, which takes the long way to get to `2**38`. Just writing `2**38` on it's own, though, takes even more shortcuts to get to the 12th-digit number `274,877,906,944`.

# Making `2^38` make sense in Python

Understanding how `pow(2,38)` reduced to `(2).__pow__(38)` is more than an academic exercise. Once we realize the interconnectedness of binary operators and magic methods, we can (at least attempt to) make the world a better place. Here's a quick example:

``````>>> import builtins
>>> class BetterInt(int):
...   def __xor__(self, exponent):
...     return self**exponent
...
>>> builtins.int = BetterInt
>>> two = int(2)
>>> two^38 # = two.__xor__(38) = 2**38
274877906944
``````

We first import the `builtins` module, which keeps track of Python's built-in classes and objects.

Then, we build a new class called `BetterInt`, inheriting all of the properties from the builtin `int` class, but defining a new implementation of the `__xor__` magic method. In other words, we're bending the universe to our will by writing our own version of the magic method Python calls to resolve the caret (`^`) operator.

Finally, just to compound the madness, we tell Python to throw away the builtin version of integers and use our `BetterInt` class instead. And this "better integer" implementation allows us to finally compute exponents just like we're used to outside of Python.

Who needs a "bitwise exclusive or" operator, anyway?