Boost logo

Boost :

Subject: Re: [boost] accurate sum accumulator (kahan)
From: Matthias Troyer (troyer_at_[hidden])
Date: 2010-07-26 16:07:18


On 26 Jul 2010, at 13:14, Topher Cooper wrote:

> First off, note that in the test case part of the inaccuracy is due to the fact that 1F-6 cannot be represented exactly in floating point. Obviously, however you do it, if you add 1000000 numbers that are not precisely equal to 1/1000000 together then the correct answer will not be 1.0.
>
> As for naming -- I'm always uncomfortable using a keyword like "accurate" -- since there are many ways to improve accuracy, with Kahan's algorithm being only one.
>
> For example: for some situations presorting the numbers in ascending order can improve accuracy.
>
> A two pass algorithm, when possible, will probably give you the same result as Kahan, with, ignoring paging, similar costs. First sum the numbers. Divide the result by the number of values. Sum the differences between each value and that mean value. Subtract the result from the original sum. Kahan requires 4 add/sub ops per value, the two-pass 3.
>
> Another technique: recursively sum the lower half and the upper half and add the results. Using an explicit stack and doing this iteratively would probably improve on Kahan in both accuracy and time. This should not be combined with an ascending sort (or if you do, use interleaved splits rather than lower/upper). Ignoring the bookkeeping, this requires a single addition per value.
>
> I'm not suggesting that any of these be added, but if they were -- what would they be called?

Why don't you just call it sum(kahan)

Matthias


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk