Hacker News new | past | comments | ask | show | jobs | submit login

in computer graphics, some people try to accumulate the transformations in 1 matrix. So A_{n+1} = T_{n} * A_{n} where T_{n} is a small transformation like a rotation around an axis

They learn by experience that they also slowly accumulate errors and end up with a transformation matrix A that's no longer orthogonal and will skew the image.

Or people try to solve large lineair systems of floating points with a naive Gaussian elimination approx and end up with noise. Same with naive iterative eigen vector calculations.




moreover.... floating point addition is not commutative, nor is is associative.


What would be an example of a floating-point addition operation that doesn't commute?


    >>> x = 7.00000000000001
    >>> x + 1 - x
    1.0000000000000009
    >>> x - x + 1
    1.0


Addition is commutative with floating point numbers, what you show is actually an associativity problem in disguise.

Subtraction is obviously not commutative, so let's rewrite as an addition.

  x + 1 - x => x + 1 + (-x)
  x - x + 1 => x + (-x) + 1
Now write the implicit parenthesis

  x + 1 + (-x) => (x + 1) + (-x)
  x + (-x) + 1 => (x + (-x)) + 1
Now since we assumed addition is commutative, let swap a few things

  (x + 1) + (-x) => (-x) + (x + 1)
  (x + (-x)) + 1 => ((-x) + x) + 1
And you get the classic associativity problem. If, by swapping things, we would have gotten the same expression, it would have been a contradiction, proving that addition was not commutative, but it is not the case here.

It means that if addition is not associative, which we know is the case, then your example doesn't prove that addition is not commutative.

Of course, I didn't prove that in general, addition is commutative, but it has no reason not to be.


You're right. it's non-associativity in disguise. You might not like the next example neither:

    NaN + 1 <> 1 + NaN 
(as NaN <> NaN)

IIRC it also breaks down with signed zeros.


I may be overlooking your point. x-x+1 is evaluated left to right like any other additive expression, and after the x-x part is evaluated, the intermediate result is zero. This would be the case with any numeric type, wouldn't it?


If you need to sum a large array of numbers, it might not be a bad idea to sort that array first.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: