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