Re: Microbenchmark: Summing over array of doubles

From: Tim Peters (tim.peters_at_gmail.com)
Date: 08/03/04 

Date: Mon, 2 Aug 2004 19:56:09 -0400
To: python-list@python.org

[Yaroslav Bulatov]
...
> A better estimate of error difference would use random digits as
> opposed to [x]*10000000, but I don't know how I would calculate exact
> answer in any reasonable amount of time. (using Decimals takes over a
> second for 4000 array (with conversion))

Google on

    floating point distillation

It's possible to compute the exact sum of a list of floats using float
arithmetic, where, ignoring overflow, the result is a minimal set of
fp numbers whose mathematical (infinite precision) sum exactly equals
the mathematical sum of the inputs.

In the worst case the best of these methods can require O(log N)
passes over the list of N inputs, but in real life they usually
converge to the result in two passes independent of N, sometimes with
a third pass but over a very short list of floats.

The better-known "Kahan summation" technique is essentially a
partially-broken computation of the two highest-order components of
one distillation pass.

A case like summing [1e100] + [1.0] * (N-1) shows that left-to-right
can deliver arbitrarily bad results (the fp sum of that is 1e100
regardless of N).

Relevant Pages