a *= b not equivalent to a = a*b

[mlz]

I've been playing with the binomial function, and found that in the below code, rs *= x does not behave the same way as rs = rs * x. When I set FAIL to True, I get a different result. Both results are below.

I had read that the two were equivalent. What am I missing?

thanks,
-= miles =-


#!/usr/bin/python2

import sys
FAIL= True if len(sys.argv)>1 else False

def bin(n,k):
rs=1
k=min(k,n-k)

for i in range(1,k+1):
if FAIL: rs *= (n-(i-1))/i # these should be the same,
else: rs = rs * (n-(i-1))/i # but apparently are not
return rs


for n in range(10):
for k in range(n+1):
print bin(n,k),
print''

------------------- output -------------------------


$ pascal2
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

$ pascal2 fail
1
1 1
1 2 1
1 3 3 1
1 4 4 4 1
1 5 10 10 5 1
1 6 12 12 12 6 1
1 7 21 21 21 21 7 1
1 8 24 48 48 48 24 8 1
1 9 36 72 72 72 72 36 9 1

[Jussi Piitulainen]

mlz writes:

> I've been playing with the binomial function, and found that in the
> below code, rs *= x does not behave the same way as rs = rs * x. When
> I set FAIL to True, I get a different result. Both results are below.
>
> I had read that the two were equivalent. What am I missing?

You don't really have rs * x on the right-hand side. You have (rs * x)/y
where rs * x is always divisible by y but x alone is not.

For the record, your actual statement was rs = rs * (n-(i-1))/i, and you
are using Python 2 where / denotes integer division.

Try 3 * 4/6 and 3 * (4/6).

[INADA Naoki]

if FAIL: rs *= (n-(i-1))/i # these should be the same,

This is equal to rs = rs * ((n-(i-1))/i)

else: rs = rs * (n-(i-1))/i # but apparently are not

This is equal to rs = (rs * (n-(i-1)))/i

> --
> https://mail.python.org/mailman/listinfo/python-list



--
INADA Naoki <songof...@gmail.com>

[mlzara...@gmail.com]

Precedence, d'oh!

rs *= (n-(i-1))/i
is equivalent to:

rs = rs * ((n-(i-1))/i)

not

rs = rs * (n-(i-1))/i

which is the same as
rs = ( rs * (n-(i-1)) ) /i


Ken Iverson was right. Precedence is a bad idea.

[Peter Otten]

mlz wrote:

> I've been playing with the binomial function, and found that in the below
> code, rs *= x does not behave the same way as rs = rs * x. When I set FAIL
> to True, I get a different result. Both results are below.
>
> I had read that the two were equivalent. What am I missing?
>
> thanks,
> -= miles =-
>
>
> #!/usr/bin/python2
>
> import sys
> FAIL= True if len(sys.argv)>1 else False
>
> def bin(n,k):
> rs=1
> k=min(k,n-k)
>
> for i in range(1,k+1):
> if FAIL: rs *= (n-(i-1))/i # these should be the same,

This is evaluated as

rs = rs * ((n - (i - 1)) / i)

> else: rs = rs * (n-(i-1))/i # but apparently are not

while this is evaluated as

rs = (rs * (n - (i - 1))/i

so the two expressions do not really result in the same calculation. A
simpler example:

>>> (2*2)/3
1
>>> 2*(2/3)
0

Now "hide" the the order of evaluation:

>>> a, b = 2, 3
>>> a *= a/b
>>> a
0
>>> a, b = 2, 3
>>> a = a*a/b
>>> a
1

[Chris Angelico]

No, precedence is not a bad idea. Making assumptions based on a lack
of precedence, now, that's a bad idea. But the problem is the
assumption :)

ChrisA

[mlzara...@gmail.com]

Yes, I just worked that out. It's the integer math that's the problem.

I guess this has been fixed in python 3, but unfortunately it seems that most people are still using python 2.

Thanks for all the help!

[mlzara...@gmail.com]

I was being facetious, but behind it is a serious point. Neither the APL nor the J languages use precedence even though their inventor, Ken Iverson, was a mathematician.

That was to support functional programming dating back to the 1970's.

However, precedence wasn't the problem in this case, it was the type conversion.

[Jussi Piitulainen]

mlzara...@gmail.com writes:

> Yes, I just worked that out. It's the integer math that's the problem.
>

> I guess this has been fixed in python 3 [- -]

Note that division in Python 3 produces approximate results (floating
point numbers). This may or may not be what you want in this exercise.
I would blame this problem entirely on the precedence issue and just do
the multiplication first. The algorithm is pretty neat that way.

(Meta) Also, please leave some relevant context so it's easier to follow
the discussion. It's a general principle, and particularly acute in
comp.lang.python where many messages fail to identify their parent.

[mlzara...@gmail.com]

Here's the key:

$ python2
Python 2.7.10 ...
>>> 1/2
0
>>>

$ python
Python 3.5.1 ...
>>> 1/2
0.5
>>> 1//2
0
>>>

I read about this awhile ago, but it's not until it bites you that you remember fully.

[Erik]

How is this related to your question? The example explicitly says Python
2 and doesn't use the '//' operator.

E.

[Erik]

On 26/08/16 08:14, mlzara...@gmail.com wrote:
>
> I was being facetious, but behind it is a serious point. Neither the APL nor the J languages use precedence even though their inventor, Ken Iverson, was a mathematician.
>
> That was to support functional programming dating back to the 1970's.

Precedence is not the issue here anyway. Both '*' and '/' have the same
precedence. The two operations in your expressions have to be evaluated
in SOME order - either left-to-right or right-to-left.


The issue is twofold:

Firstly, the compound assignments will always evaluate their RHS before
performing the assignment - this is not the same as operator precedence
- they have to, else what does Python pass to the function that knows
what the compound assignment means for that type (e.g. sequences may be
extended for '*=')? So for compound assignments there is always
effectively an implicit set of parentheses around the RHS compared to
the expression without the assignment operator (if you think of the
compound assignment as being a _part_ of the overall expression).

Secondly, the way you have chosen to layout your code has fooled your
brain into thinking that the division is performed before the
multiplication. Python doesn't care that you jammed the sub-expression
together with no whitespace ;)

E.

[Christian Gollwitzer]

Am 26.08.16 um 09:53 schrieb Erik:

It's related by the fact that a*b/c performs integer division (intended
by the OP) which gives a different result than a*(b/c) (unintended by
the OP). Floating point (as in Python 3) *also* may give a different
result, but the deviation from the "true", i.e. mathematical value, is
far less than with integer arithmetics.

Christian

[Peter Otten]

mlzara...@gmail.com wrote:

> Yes, I just worked that out. It's the integer math that's the problem.
>
> I guess this has been fixed in python 3, but unfortunately it seems that
> most people are still using python 2.

Note that you can get Python 3's default behaviour in Python 2 with

from __future__ import division

at the beginning of the module.

>>> 2/3
0
>>> from __future__ import division
>>> 2/3
0.6666666666666666

[BartC]

On 26/08/2016 08:14, mlzara...@gmail.com wrote:

> However, precedence wasn't the problem in this case, it was the type conversion.

I think it was. I was puzzled as well.

But apparently if you have:

x * = expr

That's like:

x = x * (expr) # note the parentheses

which may not always be the same as:

x = x * expr

as the latter may depends on how operators within expr relate to the
'*'. In your example, "/" within expr has the same precedence as "*" is
the "*" is done first not last.

The type conversion may be another issue, but it doesn't explain why the
results with the /same version/ of Python are different.

--
Bartc

[mlz]

Aha. That's interesting.


On Friday, August 26, 2016 at 2:11:32 AM UTC-7, Peter Otten wrote:

[mlz]

Partly it's the layout, but mathematically speaking the two should be equal.

(a*b)/c should equal a*(b/c)

The fact that they're not is surprising, because python 2 so seamlessly supports big integers in a mathematically correct way.

I consider such surprising behavior to be abstraction leak, which is probably why it has been fixed in python 3.

-= m =-


On Friday, August 26, 2016 at 12:54:02 AM UTC-7, Erik wrote:

[mlz]

It's true that a*(b/c) yields fractions which would probably accrue accuracy errors depending on how those values are implemented. For example, it is possible to represent 1/3 internally as two numbers, numerator and denominator, thus avoiding the repeating decimal (or binimal, or whatever it's called). I believe there are languages that preserve exact accuracy in this way for rational fractions. I don't know if Python is one of them.

On the other hand, (a*b)/c is safer since in this case (for the binomial coefficient) it always yields an integer.

-= m =-

On Friday, August 26, 2016 at 1:42:31 AM UTC-7, Christian Gollwitzer wrote:
> Am 26.08.16 um 09:53 schrieb Erik:

[Jussi Piitulainen]

mlz writes:

> It's true that a*(b/c) yields fractions which would probably accrue
> accuracy errors depending on how those values are implemented. For
> example, it is possible to represent 1/3 internally as two numbers,
> numerator and denominator, thus avoiding the repeating decimal (or
> binimal, or whatever it's called). I believe there are languages that
> preserve exact accuracy in this way for rational fractions. I don't
> know if Python is one of them.

Python doesn't and isn't. Exact fractions are available in the standard
library, but the notation 1/3 gives a floating point approximation.

Floating point arithmetic is usually supported directly in the hardware
in bounded space (64 bits per number). Exact rationals can acquire huge
numerators and denominators surprisingly fast, slowing the computations
down. It's a tradeoff. It's good to know about both.

> On the other hand, (a*b)/c is safer since in this case (for the
> binomial coefficient) it always yields an integer.

When you compute them in that specific way, walking the numerator down
and denominator up.

[Chris Angelico]

On Fri, Aug 26, 2016 at 8:20 PM, mlz <mlzara...@gmail.com> wrote:
> I believe there are languages that preserve exact accuracy in this way for rational fractions. I don't know if Python is one of them.

It is, but only if you explicitly request it (due to the performance
impact). Just import it:

#!/usr/bin/python2
import fractions

import sys
FAIL= True if len(sys.argv)>1 else False

def bin(n,k):
rs=1
k=min(k,n-k)

n = fractions.Fraction(n)

for i in range(1,k+1):
if FAIL: rs *= (n-(i-1))/i # these should be the same,
else: rs = rs * (n-(i-1))/i # but apparently are not
return rs


for n in range(10):
for k in range(n+1):
print bin(n,k),
print''

That's the only change you need. The arithmetic will then be done with
ratios of integers, and it'll be exact.

ChrisA