Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #79414 > unrolled thread

(-1)**1000

Back to article view | Back to comp.lang.python

Contents

  (-1)**1000 "ast" <nomail@invalid.com> - 2014-10-22 10:27 +0200
    Re: (-1)**1000 Chris Angelico <rosuav@gmail.com> - 2014-10-22 19:54 +1100
      Re: (-1)**1000 "ast" <nomail@invalid.com> - 2014-10-22 11:27 +0200
        Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 12:29 +0200
        Re: (-1)**1000 Michiel Overtoom <motoom@xs4all.nl> - 2014-10-22 12:38 +0200
        Re: (-1)**1000 Tim Chase <python.list@tim.thechases.com> - 2014-10-22 05:43 -0500
        Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 13:02 +0200
        Re: (-1)**1000 Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-22 08:23 -0600
        Re: (-1)**1000 Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-22 08:29 -0600
        Re: (-1)**1000 Ned Batchelder <ned@nedbatchelder.com> - 2014-10-22 11:01 -0400
          Re: (-1)**1000 albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-11-04 00:46 +0000
      Re: (-1)**1000 wxjmfauth@gmail.com - 2014-10-22 04:35 -0700
    Re: (-1)**1000 Peter Otten <__peter__@web.de> - 2014-10-22 11:13 +0200
    Re: (-1)**1000 Terry Reedy <tjreedy@udel.edu> - 2014-10-22 13:15 -0400
    Re: (-1)**1000 Dave Angel <davea@davea.name> - 2014-10-24 13:57 -0400
    Re: (-1)**1000 Tony the Tiger <tony@tiger.invalid> - 2014-10-26 20:07 +0000
      Re: (-1)**1000 Ned Batchelder <ned@nedbatchelder.com> - 2014-10-26 16:45 -0400
      Re: (-1)**1000 Stefan Behnel <stefan_ml@behnel.de> - 2014-10-29 20:31 +0100

#79414 — (-1)**1000

Hello

If i am writing (-1)**1000 on a python program, will the
interpreter do (-1)*(-1)*...*(-1) or something clever ?

In fact i have (-1)**N with N an integer potentially big.

I do some tests that suggest that Python is clever

thx

[toc] | [next] | [standalone]

#79418

On Wed, Oct 22, 2014 at 7:27 PM, ast <nomail@invalid.com> wrote:
> If i am writing (-1)**1000 on a python program, will the
> interpreter do (-1)*(-1)*...*(-1) or something clever ?
>
> In fact i have (-1)**N with N an integer potentially big.

Exponentiation is far more efficient than the naive implementation of
iterated multiplication. Any modern programming language on any modern
CPU architecture should be able to handle this kind of thing. But even
the naive approach is likely to be fast enough.

>>> x=1
>>> for i in range(1000000): x*=-1

I had to go as far as a million iterations before this, implemented
purely in Python with absolutely no optimization, demonstrated a
visible pause (of about a quarter second) on my not-exactly-new
Windows laptop. My Linux desktop, with a rather hotter CPU, has no
trouble with a million, so I'd have to go higher to get a pause out of
it.

And actually, about half of that time is spent in the loop - replacing
the assignment with "pass" still leaves half the iteration time.

Poor performance is a crime. Python is innocent until proven guilty.
And the burden of proof is seldom met.

ChrisA

[toc] | [prev] | [next] | [standalone]

#79424

"Chris Angelico" <rosuav@gmail.com> a écrit dans le message de 
news:mailman.15058.1413968065.18130.python-list@python.org...
> On Wed, Oct 22, 2014 at 7:27 PM, ast <nomail@invalid.com> wrote:
>> If i am writing (-1)**1000 on a python program, will the
>> interpreter do (-1)*(-1)*...*(-1) or something clever ?
>>
>> In fact i have (-1)**N with N an integer potentially big.
>
> Exponentiation is far more efficient than the naive implementation of
> iterated multiplication.

In the very particular case of (-1)**N,  I belive that Python check
the odd or even parity of N and provides the result accordingly.

I tried:
>>> (-1)**1000000000000000000000000000000000
1
>>> (-1)**1000000000000000000000000000000001
-1

and it is instantaneous

[toc] | [prev] | [next] | [standalone]

#79426

ast wrote:

> 
> "Chris Angelico" <rosuav@gmail.com> a écrit dans le message de
> news:mailman.15058.1413968065.18130.python-list@python.org...
>> On Wed, Oct 22, 2014 at 7:27 PM, ast <nomail@invalid.com> wrote:
>>> If i am writing (-1)**1000 on a python program, will the
>>> interpreter do (-1)*(-1)*...*(-1) or something clever ?
>>>
>>> In fact i have (-1)**N with N an integer potentially big.
>>
>> Exponentiation is far more efficient than the naive implementation of
>> iterated multiplication.
> 
> In the very particular case of (-1)**N,  I belive that Python check
> the odd or even parity of N and provides the result accordingly.
> 
> I tried:
>>>> (-1)**1000000000000000000000000000000000
> 1
>>>> (-1)**1000000000000000000000000000000001
> -1
> 
> and it is instantaneous

Not instantaneous once you defeat the peephole optimizer by introducing a 
variable:

$ python3 -m timeit '(-1)**10000000000000000000000000000000001'
10000000 loops, best of 3: 0.0356 usec per loop
$ python3 -m timeit -s'a = 10000000000000000000000000000000001' '(-1)**a'
100000 loops, best of 3: 3.23 usec per loop

When you increase the exponent you might discern a pattern:

$ python3 -m timeit -s 'a = 10**10' '(-1)**a'
1000000 loops, best of 3: 1.42 usec per loop
$ python3 -m timeit -s 'a = 10**100' '(-1)**a'
100000 loops, best of 3: 11.6 usec per loop
$ python3 -m timeit -s 'a = 10**1000' '(-1)**a'
10000 loops, best of 3: 101 usec per loop
$ python3 -m timeit -s 'a = 10**10000' '(-1)**a'
1000 loops, best of 3: 992 usec per loop

That looks like log(a) while a parity check takes constant time:

$ python3 -m timeit -s 'a = 10**10' 'a & 1'
10000000 loops, best of 3: 0.124 usec per loop
$ python3 -m timeit -s 'a = 10**100' 'a & 1'
10000000 loops, best of 3: 0.124 usec per loop
$ python3 -m timeit -s 'a = 10**1000' 'a & 1'
10000000 loops, best of 3: 0.122 usec per loop

[toc] | [prev] | [next] | [standalone]

#79428

On Oct 22, 2014, at 12:29, Peter Otten wrote:

> That looks like log(a) while a parity check takes constant time:
> $ python3 -m timeit -s 'a = 10**10' 'a & 1'


Do you mean 'parity' as in http://en.wikipedia.org/wiki/Parity_bit ?  Because a parity bit denotes whether the *number* of '1' bits is even or odd, not the value of the least significant bit.

Greetings,

-- 
"You can't actually make computers run faster, you can only make them do less." - RiderOfGiraffes

[toc] | [prev] | [next] | [standalone]

#79430

On 2014-10-22 12:29, Peter Otten wrote:
> That looks like log(a) while a parity check takes constant time:
> 
> $ python3 -m timeit -s 'a = 10**10' 'a & 1'
> 10000000 loops, best of 3: 0.124 usec per loop
> $ python3 -m timeit -s 'a = 10**100' 'a & 1'
> 10000000 loops, best of 3: 0.124 usec per loop
> $ python3 -m timeit -s 'a = 10**1000' 'a & 1'
> 10000000 loops, best of 3: 0.122 usec per loop

Just for the record, this is a one-bit even/odd check (which is
useful & fast in this sign-of-large-exponent case), not a parity check
(which typically counts the number of "1" bits, adds the parity bit,
and asserts the result is even)

-tkc

[toc] | [prev] | [next] | [standalone]

#79431

Michiel Overtoom wrote:

> 
> On Oct 22, 2014, at 12:29, Peter Otten wrote:
> 
>> That looks like log(a) while a parity check takes constant time:
>> $ python3 -m timeit -s 'a = 10**10' 'a & 1'
> 
> 
> Do you mean 'parity' as in http://en.wikipedia.org/wiki/Parity_bit ? 
> Because a parity bit denotes whether the *number* of '1' bits is even or
> odd, not the value of the least significant bit.

No, I meant the lsb. The OP introduced the term 'parity'; not sure if that 
was erroneous, too, or if there is an angle to the problem that escapes me.

[toc] | [prev] | [next] | [standalone]

#79442

On Wed, Oct 22, 2014 at 5:02 AM, Peter Otten <__peter__@web.de> wrote:
> Michiel Overtoom wrote:
>
>>
>> On Oct 22, 2014, at 12:29, Peter Otten wrote:
>>
>>> That looks like log(a) while a parity check takes constant time:
>>> $ python3 -m timeit -s 'a = 10**10' 'a & 1'
>>
>>
>> Do you mean 'parity' as in http://en.wikipedia.org/wiki/Parity_bit ?
>> Because a parity bit denotes whether the *number* of '1' bits is even or
>> odd, not the value of the least significant bit.
>
> No, I meant the lsb. The OP introduced the term 'parity'; not sure if that
> was erroneous, too, or if there is an angle to the problem that escapes me.

Since the OP just wrote "parity", not "parity bit", I would assume
they meant as in http://en.wikipedia.org/wiki/Parity_(mathematics)

[toc] | [prev] | [next] | [standalone]

#79443

On Wed, Oct 22, 2014 at 4:43 AM, Tim Chase
<python.list@tim.thechases.com> wrote:
> On 2014-10-22 12:29, Peter Otten wrote:
>> That looks like log(a) while a parity check takes constant time:
>>
>> $ python3 -m timeit -s 'a = 10**10' 'a & 1'
>> 10000000 loops, best of 3: 0.124 usec per loop
>> $ python3 -m timeit -s 'a = 10**100' 'a & 1'
>> 10000000 loops, best of 3: 0.124 usec per loop
>> $ python3 -m timeit -s 'a = 10**1000' 'a & 1'
>> 10000000 loops, best of 3: 0.122 usec per loop
>
> Just for the record, this is a one-bit even/odd check

Which is just a verbose way of writing "parity check", even if that
phrase is usually used in another context.

[toc] | [prev] | [next] | [standalone]

#79445

On 10/22/14 5:27 AM, ast wrote:
>
> "Chris Angelico" <rosuav@gmail.com> a écrit dans le message de
> news:mailman.15058.1413968065.18130.python-list@python.org...
>> On Wed, Oct 22, 2014 at 7:27 PM, ast <nomail@invalid.com> wrote:
>>> If i am writing (-1)**1000 on a python program, will the
>>> interpreter do (-1)*(-1)*...*(-1) or something clever ?
>>>
>>> In fact i have (-1)**N with N an integer potentially big.
>>
>> Exponentiation is far more efficient than the naive implementation of
>> iterated multiplication.
>
> In the very particular case of (-1)**N,  I belive that Python check
> the odd or even parity of N and provides the result accordingly.
>
> I tried:
>>>> (-1)**1000000000000000000000000000000000
> 1
>>>> (-1)**1000000000000000000000000000000001
> -1
>
> and it is instantaneous
>
>

Keep in mind that actually calculating the exponentiation wouldn't do 
1000000000000000000000000000000000 multiplications anyway: the clever 
way to do integer powers is by squaring based on the binary 
representation of the exponent.  It's explained here: 
http://stackoverflow.com/a/101613/14343

So even if Python is actually calculating the value, it's only doing 75 
multiplications or so.

-- 
Ned Batchelder, http://nedbatchelder.com

[toc] | [prev] | [next] | [standalone]

#80166

In article <mailman.15076.1413990100.18130.python-list@python.org>,
Ned Batchelder  <ned@nedbatchelder.com> wrote:
>On 10/22/14 5:27 AM, ast wrote:
>>
>> "Chris Angelico" <rosuav@gmail.com> a écrit dans le message de
>> news:mailman.15058.1413968065.18130.python-list@python.org...
>>> On Wed, Oct 22, 2014 at 7:27 PM, ast <nomail@invalid.com> wrote:
>>>> If i am writing (-1)**1000 on a python program, will the
>>>> interpreter do (-1)*(-1)*...*(-1) or something clever ?
>>>>
>>>> In fact i have (-1)**N with N an integer potentially big.
>>>
>>> Exponentiation is far more efficient than the naive implementation of
>>> iterated multiplication.
>>
>> In the very particular case of (-1)**N,  I belive that Python check
>> the odd or even parity of N and provides the result accordingly.
>>
>> I tried:
>>>>> (-1)**1000000000000000000000000000000000
>> 1
>>>>> (-1)**1000000000000000000000000000000001
>> -1
>>
>> and it is instantaneous
>>
>>
>
>Keep in mind that actually calculating the exponentiation wouldn't do
>1000000000000000000000000000000000 multiplications anyway: the clever
>way to do integer powers is by squaring based on the binary
>representation of the exponent.  It's explained here:
>http://stackoverflow.com/a/101613/14343
>
>So even if Python is actually calculating the value, it's only doing 75
>multiplications or so.

I'm pretty sure that if we replace -1 by 2 , it never gets at its 75-th
multiplication.

>
>--
>Ned Batchelder, http://nedbatchelder.com
>
Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#79433

Le mercredi 22 octobre 2014 10:54:51 UTC+2, Chris Angelico a écrit :
> 
> 
> 
> Poor performance is a crime. Python is innocent until proven guilty.
> And the burden of proof is seldom met.
> 
> 

>>> timeit.repeat("('abc'*1000 +'z')[:-1]")
[1.4107052484530875, 1.3924774653606349, 1.3934069318508087]
>>> timeit.repeat("('abc'*1000 +'EURO')[:-1]")
[5.427585698976522, 5.39270195514851, 5.40894516974776]
>>>

Not only this disastrous (and systematic) behaviour
is explainable, I have no problem to explain this
to those who wish to listen.

jmf

[toc] | [prev] | [next] | [standalone]

#79420

ast wrote:

> If i am writing (-1)**1000 on a python program, will the
> interpreter do (-1)*(-1)*...*(-1) or something clever ?
> 
> In fact i have (-1)**N with N an integer potentially big.
> 
> I do some tests that suggest that Python is clever

Let's see:

$ python3
Python 3.4.0 (default, Apr 11 2014, 13:05:11) 
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import dis
>>> def f():
...     return (-1)**1000
... 
>>> dis.dis(f)
  2           0 LOAD_CONST               4 (1)
              3 RETURN_VALUE

So yes, CPython replaces the expression (-1)**1000 with its value during 
compilation.

[toc] | [prev] | [next] | [standalone]

#79461

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.



-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#79597

Terry Reedy <tjreedy@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

[toc] | [prev] | [next] | [standalone]

#79724

On Wed, 22 Oct 2014 10:27:34 +0200, ast wrote:

> If i am writing (-1)**1000 on a python program, will the interpreter do
> (-1)*(-1)*...*(-1) or something clever ?

Even vs. odd. It ought to know. I would assume from a set of defined 
rules how math works.


 /Grrr
-- 
          ___                  ___
 (\_--_/)  | _ ._    _|_|_  _   |o _  _ ._
 ( 9  9 )  |(_)| |\/  |_| |(/_  ||(_|(/_|
 stripes are forever - as overripe ferrets

[toc] | [prev] | [next] | [standalone]

#79726

On 10/26/14 4:07 PM, Tony the Tiger wrote:
> On Wed, 22 Oct 2014 10:27:34 +0200, ast wrote:
>
>> If i am writing (-1)**1000 on a python program, will the interpreter do
>> (-1)*(-1)*...*(-1) or something clever ?
>
> Even vs. odd. It ought to know. I would assume from a set of defined
> rules how math works.

There is such a thing as an optimization that isn't worthwhile to 
perform, simply because it's expected to provide so little benefit.  The 
language implementors have to trade off the cost of adding the 
optimization to the implementation, against the possible benefit people 
would get from it.

Benefit in this case would have to include a guess as to how often real 
programs would hit the optimization case.

-- 
Ned Batchelder, http://nedbatchelder.com

[toc] | [prev] | [next] | [standalone]

#79939

Ned Batchelder schrieb am 26.10.2014 um 21:45:
> On 10/26/14 4:07 PM, Tony the Tiger wrote:
>> On Wed, 22 Oct 2014 10:27:34 +0200, ast wrote:
>>
>>> If i am writing (-1)**1000 on a python program, will the interpreter do
>>> (-1)*(-1)*...*(-1) or something clever ?
>>
>> Even vs. odd. It ought to know. I would assume from a set of defined
>> rules how math works.
> 
> There is such a thing as an optimization that isn't worthwhile to perform,
> simply because it's expected to provide so little benefit.  The language
> implementors have to trade off the cost of adding the optimization to the
> implementation, against the possible benefit people would get from it.
> 
> Benefit in this case would have to include a guess as to how often real
> programs would hit the optimization case.

... and also compare it to the number of cases where the optimisation
(which may, for example, need to check for an optimisable value or set of
values) slows down the generic (unoptimised) code path that is actually taken.

Even if the code impact on the implementation is small enough to be
acceptable, an optimisation for unlikely cases may provide a net-loss for
the "normal" code. So there are several reasons why an "obvious"
optimisation may be a bad idea.

Stefan

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web