Re: (-1)**1000

Path	csiph.com!usenet.pasdenom.info!dedibox.gegeweb.org!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!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; 'cpython': 0.05; 'interpreter': 0.05; 'mask': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'trailing': 0.09; 'python': 0.11; 'suggest': 0.14; 'wrote': 0.14; '-1,': 0.16; '-1.': 0.16; 'ast': 0.16; 'bit.': 0.16; 'does,': 0.16; 'integer,': 0.16; 'postive': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'reedy': 0.16; 'zeroes': 0.16; 'component': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'tests': 0.22; 'integer': 0.24; 'non': 0.24; 'first,': 0.26; 'header:X-Complaints-To:1': 0.27; 'function': 0.29; 'am,': 0.29; 'program,': 0.31; 'clever': 0.31; 'int,': 0.31; 'probably': 0.32; 'know.': 0.32; 'checking': 0.33; 'something': 0.35; 'but': 0.35; 'there': 0.35; 'accuracy': 0.36; 'done': 0.36; 'two': 0.37; 'depends': 0.38; 'improving': 0.38; 'to:addr:python- list': 0.38; 'fact': 0.38; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'above,': 0.60; 'negative': 0.60; 'numbers': 0.61; 'such': 0.63; 'choose': 0.64; 'worth': 0.66; 'bottom': 0.67; 'evaluate': 0.72; 'square': 0.74; 'special': 0.74; 'power': 0.76; 'potentially': 0.81; 'float,': 0.84
X-Injected-Via-Gmane	http://gmane.org/
To	python-list@python.org
From	Dave Angel <davea@davea.name>
Subject	Re: (-1)**1000
Date	Fri, 24 Oct 2014 13:57:08 -0400 (EDT)
Organization	news.gmane.org
References	<54476a77$0$21664$426a74cc@news.free.fr> <m28ond$bq9$1@ger.gmane.org>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
Content-Transfer-Encoding	7bit
X-Gmane-NNTP-Posting-Host	wsip-68-106-144-188.dc.dc.cox.net
X-Newsreader	PiaoHong.Usenet.Client.VIP:1.62
X-Archive	encrypt
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.15142.1414173224.18130.python-list@python.org> (permalink)
Lines	45
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1414173224 news.xs4all.nl 2960 [2001:888:2000:d::a6]:38741
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:79597

Show key headers only | View raw

Terry Reedy <tjreedy@udel.edu> Wrote in message:
> On 10/22/2014 4:27 AM, ast wrote:
>> Hello
>>
>> If i am writing (-1)**1000 on a python program, will the
>> interpreter do (-1)*(-1)*...*(-1) or something clever ?
> 
> The answer depends on the implementation.
> 
>> In fact i have (-1)**N with N an integer potentially big.
>>
>> I do some tests that suggest that Python is clever
> 
> You probably mean "CPython is clever".  Other implementations may or may 
> not have the same optimizations.
> 

I can see several potential optimizations for x**n. Some the
 CPython implementation does, others I don't know.

First, if the two component numbers are known at function compile
 time, evaluate at compile time.

If x is known at compile time to be -1, and n is a non negative
 integer, just mask the bottom bit of n, and choose -1 or 1 based
 on that bit. There are other special values, such as 0,
 -1.

If x is a power of 2, and n is an int, then count the trailing
 zeroes of x, multiply that by n, and construct a (binary) value
 with that many trailing zeroes.

If x isn't any of the above, but n is a postive int, use the
 square and multiply technique, which is of order log(n). In
 particular for n of a billion (10**9), it can be done in about 60
 multiplies.

If neither value is known at compile time,  it may still be worth
 checking for some of these, such as the last. And if x is a
 float,  the last optimization has the advantage of improving
 accuracy as well as speed.

-- 
DaveA

Thread

(-1)**1000 "ast" <nomail@invalid.com> - 2014-10-22 10:27 +0200
  Re: (-1)**1000 Chris Angelico <rosuav@gmail.com> - 2014-10-22 19:54 +1100
    Re: (-1)**1000 "ast" <nomail@invalid.com> - 2014-10-22 11:27 +0200
      Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 12:29 +0200
      Re: (-1)**1000 Michiel Overtoom <motoom@xs4all.nl> - 2014-10-22 12:38 +0200
      Re: (-1)**1000 Tim Chase <python.list@tim.thechases.com> - 2014-10-22 05:43 -0500
      Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 13:02 +0200
      Re: (-1)**1000 Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-22 08:23 -0600
      Re: (-1)**1000 Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-22 08:29 -0600
      Re: (-1)**1000 Ned Batchelder <ned@nedbatchelder.com> - 2014-10-22 11:01 -0400
        Re: (-1)**1000 albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-11-04 00:46 +0000
    Re: (-1)**1000 wxjmfauth@gmail.com - 2014-10-22 04:35 -0700
  Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 11:13 +0200
  Re: (-1)**1000 Terry Reedy <tjreedy@udel.edu> - 2014-10-22 13:15 -0400
  Re: (-1)**1000 Dave Angel <davea@davea.name> - 2014-10-24 13:57 -0400
  Re: (-1)**1000 Tony the Tiger <tony@tiger.invalid> - 2014-10-26 20:07 +0000
    Re: (-1)**1000 Ned Batchelder <ned@nedbatchelder.com> - 2014-10-26 16:45 -0400
    Re: (-1)**1000 Stefan Behnel <stefan_ml@behnel.de> - 2014-10-29 20:31 +0100

csiph-web