Hacker News Reader

Comment by mbauman | Hacker News Reader

See the one footnote: you can re-associate a list of 2046 numbers such that they sum to _any_ floating point number between 0 and 2^970.

https://discourse.julialang.org/t/array-ordering-and-naive-s...

View on HN

To be fair though, as noted further down in that thread, naive left-to-right summation is the worst case here since the tree of operations is as skewed as possible. I think that any other tree shape is better and compilers will tend to make the tree more balanced, not less, when they use associativity to enable SIMD optimizations. So while reassociation is theoretically arbitrarily bad, in practice it's probably mostly ok. Probably.

This is exactly right. Also, _all_ of the summation orderings satisfy the usual backwards-stability bounds, and so all of them are perfectly stable in normal computations.

Floating point math is fun:

  def re_add(a,b,c,d,e):
      return (a+b+c+d+e) == (2 * (c+a+b+d+e))
  
  print(re_add(1e17, -1e17, 3, 2, 1))

Reply on news.ycombinator.com