Re: [boost] accurate sum accumulator (kahan)

Subject: Re: [boost] accurate sum accumulator (kahan)
From: Paul A. Bristow (pbristow_at_[hidden])
Date: 2010-07-26 09:59:29

> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-bounces_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 1e-6f 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
[phone], mobile [phone]
pbristow_at_[hidden]