Help with map python 2

[Steven D'Aprano]

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 at ando ~]$ python2.7 -m timeit "(-1)**1000"
10000000 loops, best of 3: 0.0479 usec per loop
[steve at 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 at ando ~]$ python2.7 -m timeit -s "n = -1; m = 1000" "n**m"
1000000 loops, best of 3: 0.195 usec per loop
[steve at ando ~]$ python2.7 -m timeit -s "n = -1; m = 1000000000" "n**m"
1000000 loops, best of 3: 0.447 usec per loop
[steve at 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 at ando ~]$ python3.3 -m timeit -s "n = -1; m = 1000" "n**m"
1000000 loops, best of 3: 0.606 usec per loop
[steve at ando ~]$ python3.3 -m timeit -s "n = -1; m = 1000000000" "n**m"
1000000 loops, best of 3: 1.16 usec per loop
[steve at 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 at 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 at 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