# Does Python optimize low-power functions?

The following two functions return the same result:

x**2
x*x

But they may be computed in different ways. The first choice can accommodate non-integer powers and so it would logically proceed by taking a logarithm, multiplying by the power (in this case, 2), and then taking the anti-logarithm. But for a trivial value for the power like 2, this is clearly a wasteful choice. Just multiply x by itself, and skip the expensive log and anti-log steps.

My question is, what do Python interpreters do with power operators where the power is a small constant, like 2? Do they know to take the shortcut?

2. ### Neil CeruttiGuest

> The following two functions return the same result:
>
> x**2
> x*x
>
> But they may be computed in different ways. The first choice
> can accommodate non-integer powers and so it would logically
> proceed by taking a logarithm, multiplying by the power (in
> this case, 2), and then taking the anti-logarithm. But for a
> trivial value for the power like 2, this is clearly a wasteful
> choice. Just multiply x by itself, and skip the expensive log
> and anti-log steps.
>
> My question is, what do Python interpreters do with power
> operators where the power is a small constant, like 2? Do they
> know to take the shortcut?

It uses a couple of fast algorithms for computing powers. Here's
the excerpt with the comments identifying the algorithms used.
>From longobject.c:

2873 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
2874 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
....
2886 else {
2887 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */

The only outright optimization of the style I think your
describing that I can see is it quickly returns zero when modulus
is one.

I'm not a skilled or experienced CPython source reader, though.

--
Neil Cerutti
Neil Cerutti, Dec 6, 2013

3. ### Robert KernGuest

On 2013-12-06 19:01, Neil Cerutti wrote:
>> The following two functions return the same result:
>>
>> x**2
>> x*x
>>
>> But they may be computed in different ways. The first choice
>> can accommodate non-integer powers and so it would logically
>> proceed by taking a logarithm, multiplying by the power (in
>> this case, 2), and then taking the anti-logarithm. But for a
>> trivial value for the power like 2, this is clearly a wasteful
>> choice. Just multiply x by itself, and skip the expensive log
>> and anti-log steps.
>>
>> My question is, what do Python interpreters do with power
>> operators where the power is a small constant, like 2? Do they
>> know to take the shortcut?

>
> It uses a couple of fast algorithms for computing powers. Here's
> the excerpt with the comments identifying the algorithms used.
> From longobject.c:
>
> 2873 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
> 2874 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
> ...
> 2886 else {
> 2887 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */

It's worth noting that the *interpreter* per se is not doing this. The
implementation of the `long` object does this in its implementation of the
`__pow__` method, which the interpreter invokes. Other objects may implement
this differently and use whatever optimizations they like. They may even (ab)use
the syntax for things other than numerical exponentiation where `x**2` is not
equivalent to `x*x`. Since objects are free to do so, the interpreter itself
cannot choose to optimize that exponentiation down to multiplication.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
an underlying truth."
-- Umberto Eco
Robert Kern, Dec 6, 2013
4. ### Nick CashGuest

>My question is, what do Python interpreters do with power operators where the power is a small constant, like 2? Do they know to take the shortcut?

Nope:

Python 3.3.0 (default, Sep 25 2013, 19:28:08)
[GCC 4.7.2] on linux2
>>> import dis
>>> dis.dis(lambda x: x*x)

6 BINARY_MULTIPLY
7 RETURN_VALUE
>>> dis.dis(lambda x: x**2)

6 BINARY_POWER
7 RETURN_VALUE

The reasons why have already been answered, I just wanted to point out thatPython makes it extremely easy to check these sorts of things for yourself..
Nick Cash, Dec 6, 2013

On Friday, December 6, 2013 11:32:00 AM UTC-8, Nick Cash wrote:

> The reasons why have already been answered, I just wanted to point out that Python makes it extremely easy to check these sorts of things for yourself.

Thanks for the heads-up on the dis module, Nick. I haven't played with that one yet.
6. ### Oscar BenjaminGuest

> The following two functions return the same result:
>
> x**2
> x*x
>
> But they may be computed in different ways. The first choice can accommodate non-integer powers and so it would logically proceed by taking a logarithm, multiplying by the power (in this case, 2), and then taking the anti-logarithm. But for a trivial value for the power like 2, this is clearly awasteful choice. Just multiply x by itself, and skip the expensive log and anti-log steps.
>
> My question is, what do Python interpreters do with power operators wherethe power is a small constant, like 2? Do they know to take the shortcut?

As mentioned this will depend on the interpreter and on the type of x.
Python's integer arithmetic is exact and unbounded so switching to
floating point and using approximate logarithms is a no go if x is an
int object.

For CPython specifically, you can see here:
http://hg.python.org/cpython/file/07ef52e751f3/Objects/floatobject.c#l741
that for floats x**2 will be equivalent to x**2.0 and will be handled
by the pow function from the underlying C math library. If you read
the comments around that line you'll see that different inconsistent
math libraries can do things very differently leading to all kinds of
different problems.

For CPython if x is an int (long) then as mentioned before it is
handled by the HAC algorithm:
http://hg.python.org/cpython/file/07ef52e751f3/Objects/longobject.c#l3934

For CPython if x is a complex then it is handled roughly as you say:
for x**n if n is between -100 and 100 then multiplication is performed
using the "bit-mask exponentiation" algorithm. Otherwise it is
computed by converting to polar exponential form and using logs (see
also the two functions above this one):
http://hg.python.org/cpython/file/07ef52e751f3/Objects/complexobject.c#l151

Oscar
Oscar Benjamin, Dec 6, 2013
7. ### Michael TorrieGuest

On 12/06/2013 12:32 PM, Nick Cash wrote:
> Nope:
>
> Python 3.3.0 (default, Sep 25 2013, 19:28:08)
> [GCC 4.7.2] on linux2
>>>> import dis
>>>> dis.dis(lambda x: x*x)

> 1 0 LOAD_FAST 0 (x)
> 6 BINARY_MULTIPLY
> 7 RETURN_VALUE
>>>> dis.dis(lambda x: x**2)

> 1 0 LOAD_FAST 0 (x)
> 6 BINARY_POWER
> 7 RETURN_VALUE
>
>
> The reasons why have already been answered, I just wanted to point
> out that Python makes it extremely easy to check these sorts of
> things for yourself.

But this is just the interpreter bytecode that dis is showing. It's not
showing the underlying implementation of binary_power, for example.
That could be defined in C code with any number of optimizations, and
indeed it appears that some are being done. dis is great for showing
how python code breaks down, but it can't tell you much about the code
that underlies the byte codes themselves.
Michael Torrie, Dec 8, 2013