simp1eton's blog

Does order of division matter in computer arithmetic?
By simp1eton, 13 years ago, In English
Hi all, I would like to ask the following qn:

In a computer, will

x / (a * b * c * d * e)

give a different solution from

x / a / b / c / d / e

where x,a,b,c,d,e are all integer data types? Since values are rounded down, I was wondering if that would cost the 2nd method of division to reach a smaller value than the 1st method if too much rounding is done.

Intuitively, it seems that it should not matter, but I cannot really prove it. Can someone help me out? Thanks!
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Let x be (a*b*c*d*e)*q + r where r is remainder of the division x / (a*b*c*d*e).
Then x/a is (b*c*d*e)*q + [r/a], where [x] is rounding down of float value.
        x/a/b is (c*d*e)*q + [[r/a]/b]
        ...
        x/a/b/c/d/e is q+[[[[[r/a]/b]/c]/d]/e].
As r is strictly less than a*b*c*d*e, [[[[[r/a]/b]/c]/d]/e]=0.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Yes, it can give different results. There're several problems here:
  1. Overflow. If a = b = c = d = e = 109, a· b· c· d· e is really larger than maximal value of int. So, result is undefined
  2. Rounding together with negative numbers. For example, 3/2/-1=1/-1=-1, but 3/(2·(-1))=3/(-2)=-2. UPD: it isn't correct in C/C++ (maybe Java), but correct in Python, because in C/C++ 3/(-2)=-1. Thanks to VladBelous
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi all,

Thanks for your comments. Actually, what I was asking is whether

floor(x / (a * b * c * d * e))

in normal arithmetic is the same as

x / a / b / c / d / e

in computer arithmetic.

But you have still managed to answer my question. Thanks everyone! So unless I am dealing with negative numbers in Python, this should work fine.
→ Reply