(-1)**1000

[Dave Angel]

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,
 -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