[J3] [EXTERNAL] Re: (SC22WG5.6114) Kahan paper

[Van Snyder]

On Thu, 2019-07-25 at 22:44 -0600, Ondřej Čertík via J3 wrote:
> So we have to write the code in a way that will still work when such
> optimizations are applied. So we analyze the array that is being
> summed, and we notice that the first term is ~5000, the last one is
> ~1e-12. Summing such numbers greatly depends on the way they are
> summed. So we first sum the first few big numbers, say 600, and then
> we sum the rest.

Sure, competent numerical methods should be used.  If you know Kahan's
record, you know that he knows competent numerical methods.

Kahan's example is only one example.  It doesn't cover every instance of
the problem -- that processors do not respect the integrity of
parentheses, probably to make a benchmark a tiny bit faster.

Siegfried Rump's method to compute a correctly-rounded dot product is
another one that is ruined by processors not respecting parentheses.  I
don't know whether it can be repaired by computing all the products and
then sorting them before accumulating them.  This requires O(n) work
space.  If a real sort is done, the complexity rises to O(n log n).  A
coarse binning might work, still giving O(n) with a larger coefficient.