Ticket #4471: patch.txt

File patch.txt, 4.3 KB (added by mendola@…, 12 years ago)

patch for kahan sum

Line 
1Index: boost/accumulators/statistics/sum_kahan.hpp
2===================================================================
3--- boost/accumulators/statistics/sum_kahan.hpp (revision 0)
4+++ boost/accumulators/statistics/sum_kahan.hpp (revision 0)
5@@ -0,0 +1,91 @@
6+///////////////////////////////////////////////////////////////////////////////
7+// sum_kahan.hpp
8+//
9+// Copyright 2010 Gaetano Mendola. Distributed under the Boost
10+// Software License, Version 1.0. (See accompanying file
11+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
12+
13+#ifndef BOOST_ACCUMULATORS_STATISTICS_SUM_KAHAN_HPP_EAN_26_07_2010
14+#define BOOST_ACCUMULATORS_STATISTICS_SUM_KAHAN_HPP_EAN_26_07_2010
15+
16+#include <boost/accumulators/framework/accumulator_base.hpp>
17+#include <boost/accumulators/framework/parameters/sample.hpp>
18+#include <boost/numeric/conversion/cast.hpp>
19+
20+namespace boost { namespace accumulators
21+{
22+
23+namespace impl
24+{
25+
26+template<typename Sample>
27+struct sum_kahan_impl
28+ : accumulator_base
29+{
30+ typedef Sample result_type;
31+
32+ ////////////////////////////////////////////////////////////////////////////
33+ // sum_kahan_impl
34+ /**
35+ @brief Kahan summation algorithm
36+
37+ Kahan algorithm reduces the numerical error obtained with standard
38+ sequential sum.
39+
40+ */
41+ template<typename Args>
42+ sum_kahan_impl(Args const & args)
43+ : sum(args[sample | Sample()]),
44+ compensation(boost::numeric_cast<Sample>(0.0))
45+ {
46+ }
47+
48+ template<typename Args>
49+ void operator ()(Args const & args)
50+ {
51+ const Sample myTmp1 = args[sample] - this->compensation;
52+ const Sample myTmp2 = this->sum + myTmp1;
53+ this->compensation = (myTmp2 - this->sum) - myTmp1;
54+ this->sum = myTmp2;
55+ }
56+
57+ result_type result(dont_care) const
58+ {
59+ return this->sum;
60+ }
61+private:
62+ Sample sum;
63+ Sample compensation;
64+};
65+
66+} // namespace impl
67+
68+///////////////////////////////////////////////////////////////////////////////
69+// tag::sum_kahan
70+namespace tag
71+{
72+
73+ struct sum_kahan
74+ : depends_on<>
75+ {
76+ /// INTERNAL ONLY
77+ ///
78+ typedef impl::sum_kahan_impl< mpl::_1 > impl;
79+ };
80+} // namespace tag
81+
82+///////////////////////////////////////////////////////////////////////////////
83+// extract::sum_kahan
84+namespace extract
85+{
86+ extractor<tag::sum_kahan> const sum_kahan = {};
87+
88+ BOOST_ACCUMULATORS_IGNORE_GLOBAL(sum_kahan)
89+} // namespace extract
90+
91+using extract::sum_kahan;
92+
93+}} // namespace boost::accumulators
94+
95+#endif
96+
97Index: libs/accumulators/test/sum_kahan.cpp
98===================================================================
99--- libs/accumulators/test/sum_kahan.cpp (revision 0)
100+++ libs/accumulators/test/sum_kahan.cpp (revision 0)
101@@ -0,0 +1,41 @@
102+// (C) Copyright Gaetano Mendola 2010.
103+// Use, modification and distribution are subject to the
104+// Boost Software License, Version 1.0. (See accompanying file
105+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
106+
107+#include <boost/test/unit_test.hpp>
108+#include <boost/accumulators/accumulators.hpp>
109+#include <boost/accumulators/statistics/stats.hpp>
110+#include <boost/accumulators/statistics/sum_kahan.hpp>
111+
112+using namespace boost;
113+using namespace unit_test;
114+using namespace accumulators;
115+
116+///////////////////////////////////////////////////////////////////////////////
117+// test_stat
118+//
119+void test_stat()
120+{
121+ accumulator_set<float, stats<tag::sum_kahan> > acc;
122+
123+ BOOST_CHECK_EQUAL(0.0f, sum_kahan(acc));
124+
125+ for (size_t i = 0; i < 1e6; ++i) {
126+ acc(1e-6f);
127+ }
128+
129+ BOOST_CHECK_EQUAL(1.0f, sum_kahan(acc));
130+}
131+
132+///////////////////////////////////////////////////////////////////////////////
133+// init_unit_test_suite
134+//
135+test_suite* init_unit_test_suite( int argc, char* argv[] )
136+{
137+ test_suite *test = BOOST_TEST_SUITE("sum kahan test");
138+
139+ test->add(BOOST_TEST_CASE(&test_stat));
140+
141+ return test;
142+}
143Index: libs/accumulators/test/Jamfile.v2
144===================================================================
145--- libs/accumulators/test/Jamfile.v2 (revision 64372)
146+++ libs/accumulators/test/Jamfile.v2 (working copy)
147@@ -50,6 +50,7 @@
148 [ run rolling_mean.cpp ]
149 [ run skewness.cpp ]
150 [ run sum.cpp ]
151+ [ run sum_kahan.cpp ]
152 [ run tail.cpp ]
153 [ run tail_mean.cpp ]
154 [ run tail_quantile.cpp ]