Terry Reedy <tjre...@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 -- https://mail.python.org/mailman/listinfo/python-list