Re: Does Python optimize low-power functions?

Path	csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<python-python-list@m.gmane.org>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.002
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'algorithm': 0.04; 'cpython': 0.05; 'subject:Python': 0.06; 'binary': 0.07; 'computed': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:Does': 0.09; 'used.': 0.09; 'python': 0.11; '2),': 0.16; 'excerpt': 0.16; 'itself,': 0.16; 'powers.': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'wrote:': 0.18; '(in': 0.22; 'header:User-Agent:1': 0.23; 'accommodate': 0.24; 'skip': 0.24; 'question': 0.24; 'source': 0.25; 'header:X-Complaints-To:1': 0.27; 'quickly': 0.29; "i'm": 0.30; 'comments': 0.31; 'operators': 0.31; 'though.': 0.31; 'trivial': 0.31; 'proceed': 0.33; 'style': 0.33; 'case,': 0.35; 'computing': 0.35; 'but': 0.35; 'charset:us-ascii': 0.36; 'subject:?': 0.36; 'two': 0.37; 'to:addr:python-list': 0.38; 'expensive': 0.39; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'algorithms': 0.60; 'url:about': 0.61; 'john': 0.61; 'first': 0.61; 'different': 0.65; 'taking': 0.65; 'url:pdf': 0.68; 'power': 0.76; 'multiplying': 0.84; 'steps.': 0.91; 'choice.': 0.93
X-Injected-Via-Gmane	http://gmane.org/
To	python-list@python.org
From	Neil Cerutti <neilc@norwich.edu>
Subject	Re: Does Python optimize low-power functions?
Date	Fri, 6 Dec 2013 19:01:26 +0000 (UTC)
Organization	Norwich University
References	<5ea86e1b-f5b5-49d1-acfb-22ee4d9a1f16@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
X-Gmane-NNTP-Posting-Host	jackman.norwich.edu
User-Agent	slrn/0.9.9p1/mm/ao (Win32)
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.3660.1386356539.18130.python-list@python.org> (permalink)
Lines	38
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1386356539 news.xs4all.nl 2947 [2001:888:2000:d::a6]:56577
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:61177

Show key headers only | View raw

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) */

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

Thread

Does Python optimize low-power functions? John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-06 10:16 -0800
  Re: Does Python optimize low-power functions? Neil Cerutti <neilc@norwich.edu> - 2013-12-06 19:01 +0000
  Re: Does Python optimize low-power functions? Robert Kern <robert.kern@gmail.com> - 2013-12-06 19:12 +0000
  RE: Does Python optimize low-power functions? Nick Cash <nick.cash@npcinternational.com> - 2013-12-06 19:32 +0000
    Re: Does Python optimize low-power functions? John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-06 11:43 -0800
  Re: Does Python optimize low-power functions? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-12-06 20:57 +0000
  Re: Does Python optimize low-power functions? Michael Torrie <torriem@gmail.com> - 2013-12-07 19:00 -0700

csiph-web