Re: (-1)**1000
In article mailman.15076.1413990100.18130.python-l...@python.org, Ned Batchelder n...@nedbatchelder.com wrote: On 10/22/14 5:27 AM, ast wrote: Chris Angelico ros...@gmail.com a écrit dans le message de news:mailman.15058.1413968065.18130.python-l...@python.org... On Wed, Oct 22, 2014 at 7:27 PM, ast nom...@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)**10 1 (-1)**11 -1 and it is instantaneous Keep in mind that actually calculating the exponentiation wouldn't do 10 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@spearc.xs4all.nl =n http://home.hccnet.nl/a.w.m.van.der.horst -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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
Re: (-1)**1000
- Original Message - From: ast nom...@invalid.com To: python-list@python.org Sent: Wednesday, 22 October, 2014 10:27:34 AM Subject: (-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 Python will yield the correct results. That is the most clever thing to do. If you really worried about execution speed (I assume that what your question implies), Python may not be the language you need. However, know that there are these modules numpy and scipy which are used by the scientific community which provide a python interface (it's a python module) but most of the heavy lifting is done in C (you can embed C in python code). For instance http://docs.scipy.org/doc/numpy/reference/generated/numpy.power.html Use this module if speed is what you're looking for. JM -- IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you. -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
On Wed, Oct 22, 2014 at 7:27 PM, ast nom...@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(100): 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
Chris Angelico ros...@gmail.com a écrit dans le message de news:mailman.15058.1413968065.18130.python-l...@python.org... On Wed, Oct 22, 2014 at 7:27 PM, ast nom...@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)**10 1 (-1)**11 -1 and it is instantaneous -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
ast wrote: Chris Angelico ros...@gmail.com a écrit dans le message de news:mailman.15058.1413968065.18130.python-l...@python.org... On Wed, Oct 22, 2014 at 7:27 PM, ast nom...@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)**10 1 (-1)**11 -1 and it is instantaneous Not instantaneous once you defeat the peephole optimizer by introducing a variable: $ python3 -m timeit '(-1)**101' 1000 loops, best of 3: 0.0356 usec per loop $ python3 -m timeit -s'a = 101' '(-1)**a' 10 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' 100 loops, best of 3: 1.42 usec per loop $ python3 -m timeit -s 'a = 10**100' '(-1)**a' 10 loops, best of 3: 11.6 usec per loop $ python3 -m timeit -s 'a = 10**1000' '(-1)**a' 1 loops, best of 3: 101 usec per loop $ python3 -m timeit -s 'a = 10**1' '(-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' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**100' 'a 1' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**1000' 'a 1' 1000 loops, best of 3: 0.122 usec per loop -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**100' 'a 1' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**1000' 'a 1' 1000 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
On Wed, Oct 22, 2014 at 5:02 AM, Peter Otten __pete...@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) -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
On Wed, Oct 22, 2014 at 4:43 AM, Tim Chase python.l...@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' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**100' 'a 1' 1000 loops, best of 3: 0.124 usec per loop $ python3 -m timeit -s 'a = 10**1000' 'a 1' 1000 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. -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
On 10/22/14 5:27 AM, ast wrote: Chris Angelico ros...@gmail.com a écrit dans le message de news:mailman.15058.1413968065.18130.python-l...@python.org... On Wed, Oct 22, 2014 at 7:27 PM, ast nom...@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)**10 1 (-1)**11 -1 and it is instantaneous Keep in mind that actually calculating the exponentiation wouldn't do 10 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: (-1)**1000
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 -- https://mail.python.org/mailman/listinfo/python-list
