
Boost : 
Subject: Re: [boost] accurate sum accumulator (kahan)
From: Paul A. Bristow (pbristow_at_[hidden])
Date: 20100726 09:59:29
> Original Message
> From: boostbounces_at_[hidden] [mailto:boostbounces_at_[hidden]] On Behalf Of Gaetano Mendola
> Sent: Sunday, July 25, 2010 4:24 PM
> To: boost_at_[hidden]
> Subject: [boost] accurate sum accumulator (kahan)
>
> Hi all,
> I had to implement in terms of boost accumulators the Kahan
> summation algorithm. I will paste at the end of this message
> the accumulator, the feature and the extractor source code.
>
> This accumulator reduces the numerical error obtained with
> standard sequential sum, as example the sum of 1e6f elements
> equal to 1e6f should give 1.0f, this is the results obtained
> with sum and sum_kahan:
>
> tag::sum: 1.009038925
> tag::sum_kahan: 1.000000000
>
> I'm not sure if that sum_kahan is worth to be inserted in the
> accumulators provided with boost, I'm not an expert of
> boost:accumulators (I just followed the guide to make this new
> accumulator) so not sure if you prefer to have a fast_sum
> and an accurate_sum instead of sum and sum_kahan.
<snip>
I think it would be an excellent idea to include both.
I fear that tests on the appropriate NIST datasets would show the existing 'fast' algorithm to perform badly.
http://www.itl.nist.gov/div898/strd/
Whereas I would expect your Kahan algorithm version to do much better.
It would be in keeping with Boost tradition to be (or able to be) accurate.
Some people would also like to know the accurate_sum compute time cost over existing (fast) sum
(I presume there is some?).
It would need some documentation on when and why one might need to prefer the accurate version.
Paul
PS As for naming, I'd vote for sum and accurate_sum (to keep backward compatibility).
 Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow_at_[hidden]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk