1 /////////////////////////////////////////////////////////////////////////////// 2 // sum_kahan.hpp 3 // 4 // Copyright 2010 Gaetano Mendola, 2011 Simon West. Distributed under the Boost 5 // Software License, Version 1.0. (See accompanying file 6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 7 8 #ifndef BOOST_ACCUMULATORS_STATISTICS_SUM_KAHAN_HPP_EAN_26_07_2010 9 #define BOOST_ACCUMULATORS_STATISTICS_SUM_KAHAN_HPP_EAN_26_07_2010 10 11 #include <boost/accumulators/framework/accumulator_base.hpp> 12 #include <boost/accumulators/framework/parameters/sample.hpp> 13 #include <boost/accumulators/statistics_fwd.hpp> 14 #include <boost/accumulators/statistics/sum.hpp> 15 #include <boost/accumulators/statistics/weighted_sum_kahan.hpp> 16 #include <boost/numeric/conversion/cast.hpp> 17 18 namespace boost { namespace accumulators 19 { 20 21 namespace impl 22 { 23 24 #if _MSC_VER > 1400 25 # pragma float_control(push) 26 # pragma float_control(precise, on) 27 #endif 28 29 template<typename Sample, typename Tag> 30 struct sum_kahan_impl 31 : accumulator_base 32 { 33 typedef Sample result_type; 34 35 //////////////////////////////////////////////////////////////////////////// 36 // sum_kahan_impl 37 /** 38 @brief Kahan summation algorithm 39 40 The Kahan summation algorithm reduces the numerical error obtained with standard 41 sequential sum. 42 43 */ 44 template<typename Args> sum_kahan_implboost::accumulators::impl::sum_kahan_impl45 sum_kahan_impl(Args const & args) 46 : sum(args[parameter::keyword<Tag>::get() | Sample()]), 47 compensation(boost::numeric_cast<Sample>(0.0)) 48 { 49 } 50 51 template<typename Args> 52 void 53 #if BOOST_ACCUMULATORS_GCC_VERSION > 40305 54 __attribute__((__optimize__("no-associative-math"))) 55 #endif operator ()boost::accumulators::impl::sum_kahan_impl56 operator ()(Args const & args) 57 { 58 const Sample myTmp1 = args[parameter::keyword<Tag>::get()] - this->compensation; 59 const Sample myTmp2 = this->sum + myTmp1; 60 this->compensation = (myTmp2 - this->sum) - myTmp1; 61 this->sum = myTmp2; 62 } 63 resultboost::accumulators::impl::sum_kahan_impl64 result_type result(dont_care) const 65 { 66 return this->sum; 67 } 68 69 // make this accumulator serializeable 70 template<class Archive> serializeboost::accumulators::impl::sum_kahan_impl71 void serialize(Archive & ar, const unsigned int file_version) 72 { 73 ar & sum; 74 ar & compensation; 75 } 76 77 private: 78 Sample sum; 79 Sample compensation; 80 }; 81 82 #if _MSC_VER > 1400 83 # pragma float_control(pop) 84 #endif 85 86 } // namespace impl 87 88 /////////////////////////////////////////////////////////////////////////////// 89 // tag::sum_kahan 90 // tag::sum_of_weights_kahan 91 // tag::sum_of_variates_kahan 92 // 93 namespace tag 94 { 95 96 struct sum_kahan 97 : depends_on<> 98 { 99 /// INTERNAL ONLY 100 /// 101 typedef impl::sum_kahan_impl< mpl::_1, tag::sample > impl; 102 }; 103 104 struct sum_of_weights_kahan 105 : depends_on<> 106 { 107 typedef mpl::true_ is_weight_accumulator; 108 /// INTERNAL ONLY 109 /// 110 typedef accumulators::impl::sum_kahan_impl<mpl::_2, tag::weight> impl; 111 }; 112 113 template<typename VariateType, typename VariateTag> 114 struct sum_of_variates_kahan 115 : depends_on<> 116 { 117 /// INTERNAL ONLY 118 /// 119 typedef mpl::always<accumulators::impl::sum_kahan_impl<VariateType, VariateTag> > impl; 120 }; 121 122 } // namespace tag 123 124 /////////////////////////////////////////////////////////////////////////////// 125 // extract::sum_kahan 126 // extract::sum_of_weights_kahan 127 // extract::sum_of_variates_kahan 128 // 129 namespace extract 130 { 131 extractor<tag::sum_kahan> const sum_kahan = {}; 132 extractor<tag::sum_of_weights_kahan> const sum_of_weights_kahan = {}; 133 extractor<tag::abstract_sum_of_variates> const sum_of_variates_kahan = {}; 134 135 BOOST_ACCUMULATORS_IGNORE_GLOBAL(sum_kahan) 136 BOOST_ACCUMULATORS_IGNORE_GLOBAL(sum_of_weights_kahan) 137 BOOST_ACCUMULATORS_IGNORE_GLOBAL(sum_of_variates_kahan) 138 } // namespace extract 139 140 using extract::sum_kahan; 141 using extract::sum_of_weights_kahan; 142 using extract::sum_of_variates_kahan; 143 144 // sum(kahan) -> sum_kahan 145 template<> 146 struct as_feature<tag::sum(kahan)> 147 { 148 typedef tag::sum_kahan type; 149 }; 150 151 // sum_of_weights(kahan) -> sum_of_weights_kahan 152 template<> 153 struct as_feature<tag::sum_of_weights(kahan)> 154 { 155 typedef tag::sum_of_weights_kahan type; 156 }; 157 158 // So that sum_kahan can be automatically substituted with 159 // weighted_sum_kahan when the weight parameter is non-void. 160 template<> 161 struct as_weighted_feature<tag::sum_kahan> 162 { 163 typedef tag::weighted_sum_kahan type; 164 }; 165 166 template<> 167 struct feature_of<tag::weighted_sum_kahan> 168 : feature_of<tag::sum> 169 {}; 170 171 // for the purposes of feature-based dependency resolution, 172 // sum_kahan provides the same feature as sum 173 template<> 174 struct feature_of<tag::sum_kahan> 175 : feature_of<tag::sum> 176 { 177 }; 178 179 // for the purposes of feature-based dependency resolution, 180 // sum_of_weights_kahan provides the same feature as sum_of_weights 181 template<> 182 struct feature_of<tag::sum_of_weights_kahan> 183 : feature_of<tag::sum_of_weights> 184 { 185 }; 186 187 template<typename VariateType, typename VariateTag> 188 struct feature_of<tag::sum_of_variates_kahan<VariateType, VariateTag> > 189 : feature_of<tag::abstract_sum_of_variates> 190 { 191 }; 192 193 }} // namespace boost::accumulators 194 195 #endif 196 197