# (-1)**1000

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