[accumulators] Kahan algorithmic variants of sum_impl, mean_impl?
From a look at boost::accumulators::impl::sum_impl [1] it appears a straightforward, fast 'sum += value' is used to accumulate the running sum. That can fall prey to numerical errors if the sum is large and the value is small. A slower but more precise summation is possible using the Kahan summation algorithm [2].
Has anyone implemented a Kahan-based variant for either sum_impl or mean_impl [3]? Assuming not, other than to mimic existing code, any implementation suggestions? One gotcha for Kahan summation is that optimization levels employing additive associativity can spoil the computation. Are there other places in the Boost sources where this has become an issue and where I might look for a portable way around it? Thanks, Rhys [1] http://svn.boost.org/svn/boost/trunk/boost/accumulators/statistics/sum.hpp [2] http://en.wikipedia.org/wiki/Kahan_summation_algorithm [3] http://svn.boost.org/svn/boost/trunk/boost/accumulators/statistics/mean.hpp
On 9/30/2011 7:28 AM, Rhys Ulerich wrote:
From a look at boost::accumulators::impl::sum_impl [1] it appears a straightforward, fast 'sum += value' is used to accumulate the running sum. That can fall prey to numerical errors if the sum is large and the value is small. A slower but more precise summation is possible using the Kahan summation algorithm [2].
Has anyone implemented a Kahan-based variant for either sum_impl or mean_impl [3]?
sum_kahan: http://www.boost.org/doc/libs/1_47_0/doc/html/accumulators/reference.html#he... You can get a kahan mean by putting both sum_kahan and mean in the accumulator set, since sum_kahan satisfies the sum dependency. sum_kahan is new in 1.47, thanks for Gaetano Mendola and Simon West. -- Eric Niebler BoostPro Computing http://www.boostpro.com
participants (2)
-
Eric Niebler
-
Rhys Ulerich