Dave Angel davea at davea.name
Fri Oct 24 19:57:08 CEST 2014

Terry Reedy <tjreedy at 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,

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

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.


More information about the Python-list mailing list