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: 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 On 2013-12-06, John Ladasky 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