Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #79597

Re: (-1)**1000

Show all headers | 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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