Terry Reedy wrote: > On 1/5/2015 6:33 AM, flebber wrote: >> >>> You could do what mathematicians do when they deal with alternating >>> signs: they raise -1 to the power of the index to get an appropriate >>> multiplier. >>> >>> >>> [ n * (-1) ** n for n in range(10) ] >>> [0, -1, 2, -3, 4, -5, 6, -7, 8, -9] > > Mathematicians operating in the timeless Platonic universe of > mathemtical forms are not concerned with such droll issues as > computation time. I think most regard '(-1)**n' as an abbreviation for > '(-1 if odd(n) else 1)', where odd(n) is regarded as an O(1) operation, > not as an indication to actually raise -1 to an arbitrarily large power. > which could take an arbitrarily long time.
Theoretically it could, but in practical terms no programming language would use such a poor implementation. At worst, you should expect n**m to take no more than O(log m) multiplications, and in the specific case of n == 1 or -1, you might even hope for constant time. How does CPython go? [steve@ando ~]$ python2.7 -m timeit "(-1)**1000" 10000000 loops, best of 3: 0.0479 usec per loop [steve@ando ~]$ python2.7 -m timeit "(-1)**1000000000" 10000000 loops, best of 3: 0.0477 usec per loop But wait! Maybe I'm tripping over the keyhole optimizer. Let's try again: [steve@ando ~]$ python2.7 -m timeit -s "n = -1; m = 1000" "n**m" 1000000 loops, best of 3: 0.195 usec per loop [steve@ando ~]$ python2.7 -m timeit -s "n = -1; m = 1000000000" "n**m" 1000000 loops, best of 3: 0.447 usec per loop [steve@ando ~]$ python2.7 -m timeit -s "n = -1; m = 1000000000000000" "n**m" 100000 loops, best of 3: 9.32 usec per loop So it appears that CPython 2.7 eschews some possible ** optimizations, but even so, it's pretty fast. Increasing the power by a factor of one million only doubles the time, so long as the power is an int. Increasing it by another factor of a million makes the power a long, and the time taken increases by a factor of about 20. But in absolute terms, it's still very fast: less than 10 microseconds. How does Python 3.3 go? For small powers, it is slower than 2.7, but for large powers, it is faster. [steve@ando ~]$ python3.3 -m timeit -s "n = -1; m = 1000" "n**m" 1000000 loops, best of 3: 0.606 usec per loop [steve@ando ~]$ python3.3 -m timeit -s "n = -1; m = 1000000000" "n**m" 1000000 loops, best of 3: 1.16 usec per loop [steve@ando ~]$ python3.3 -m timeit -s "n = -1; m = 1000000000000000" "n**m" 1000000 loops, best of 3: 1.97 usec per loop Let's keep going: [steve@ando ~]$ python3.3 -m timeit -s "n = -1; m = 10**100 + 1" "n**m" 100000 loops, best of 3: 9.47 usec per loop [steve@ando ~]$ python3.3 -m timeit -s "n = -1; m = 10**1000 + 1" "n**m" 10000 loops, best of 3: 83.9 usec per loop I don't think that this will be a problem in practical terms. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
