Path: csiph.com!usenet.pasdenom.info!news.albasani.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Robert Kern <robert.kern@gmail.com>
Subject: Re: Does Python optimize low-power functions?
Date: Fri, 06 Dec 2013 19:12:30 +0000
References: <5ea86e1b-f5b5-49d1-acfb-22ee4d9a1f16@googlegroups.com> <l7t6u6$4ef$1@ger.gmane.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:24.0) Gecko/20100101 Thunderbird/24.1.1
In-Reply-To: <l7t6u6$4ef$1@ger.gmane.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3661.1386357170.18130.python-list@python.org>
Lines: 46
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:61178

On 2013-12-06 19:01, Neil Cerutti wrote:
> On 2013-12-06, John Ladasky <john_ladasky@sbcglobal.net> 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) */
> 2875         /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
> ...
> 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
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco