template<typename T = double, unsigned
int N = 1>
class ROOT::Math::KahanSum< T, N >
The Kahan summation is a compensated summation algorithm, which significantly reduces numerical errors when adding a sequence of finite-precision floating point numbers.
This is done by keeping a separate running compensation (a variable to accumulate small errors).
Auto-vectorisable accumulation
This class can internally use multiple accumulators (template parameter N). When filled from a collection that supports index access from a contiguous block of memory, compilers such as gcc, clang and icc can auto-vectorise the accumulation. This happens by cycling through the internal accumulators based on the value of "`index % N`", so N accumulators can be filled from a block of N numbers in a single instruction.
The usage of multiple accumulators might slightly increase the precision in comparison to the single-accumulator version with N = 1. This depends on the order and magnitude of the numbers being accumulated. Therefore, in rare cases, the accumulation result can change in dependence of N, even when the data are identical. The magnitude of such differences is well below the precision of the floating point type, and will therefore mostly show in the compensation sum(see Carry()). Increasing the number of accumulators therefore only makes sense to speed up the accumulation, but not to increase precision.
- Parameters
-
| T | The type of the values to be accumulated. |
| N | Number of accumulators. Defaults to 1. Ideal values are the widths of a vector register on the relevant architecture. Depending on the instruction set, good values are:
- AVX2-float: 8
- AVX2-double: 4
- AVX512-float: 16
- AVX512-double: 8
|
Examples
std::vector<double> numbers(1000);
for (std::size_t i=0; i<1000; ++i) {
numbers[i] = rand();
}
k.
Add(numbers.begin(), numbers.end());
The Kahan summation is a compensated summation algorithm, which significantly reduces numerical error...
void Add(T x)
Single-element accumulation. Will not vectorise.
double offset = 10.;
static KahanSum< T, N > Accumulate(Iterator begin, Iterator end, T initialValue=T{})
Iterate over a range and return an instance of a KahanSum.
Definition at line 141 of file Util.h.
|
| template<class Iterator> |
| | KahanSum (Iterator sumBegin, Iterator sumEnd, Iterator carryBegin, Iterator carryEnd) |
| | Initialise the sum with a pre-existing state.
|
| template<unsigned int M> |
| | KahanSum (KahanSum< T, M > const &other) |
| | Constructor to create a KahanSum from another KahanSum with a different number of accumulators.
|
| | KahanSum (T initialSumValue, T initialCarryValue) |
| | Initialise with a sum value and a carry value.
|
| | KahanSum (T initialValue=T{}) |
| | Initialise the sum.
|
| template<class Container_t> |
| void | Add (const Container_t &inputs) |
| | Fill from a container that supports index access.
|
| template<class Iterator> |
| void | Add (Iterator begin, Iterator end) |
| | Accumulate from a range denoted by iterators.
|
| void | Add (T x) |
| | Single-element accumulation. Will not vectorise.
|
| void | AddIndexed (T input, std::size_t index) |
| | Add input to the sum.
|
| T | Carry () const |
| template<typename U, unsigned int M> |
| bool | operator!= (KahanSum< U, M > const &other) const |
| template<typename U, unsigned int M> |
| KahanSum< T, N > & | operator+= (const KahanSum< U, M > &other) |
| | Add other KahanSum into accumulator.
|
| KahanSum< T, N > & | operator+= (T arg) |
| | Add arg into accumulator. Does not vectorise.
|
| KahanSum< T, N > | operator- () |
| template<typename U, unsigned int M> |
| KahanSum< T, N > & | operator-= (KahanSum< U, M > const &other) |
| | Subtract other KahanSum.
|
| template<typename U, unsigned int M> |
| bool | operator== (KahanSum< U, M > const &other) const |
| T | Result () const |
| T | Sum () const |
template<typename T = double, unsigned
int N = 1>
template<typename U, unsigned
int M>
Add other KahanSum into accumulator.
Does not vectorise.
Based on KahanIncrement from: Y. Tian, S. Tatikonda and B. Reinwald, "Scalable and Numerically Stable Descriptive Statistics in SystemML," 2012 IEEE 28th International Conference on Data Engineering, 2012, pp. 1351-1359, doi: 10.1109/ICDE.2012.12. Note that while Tian et al. add the carry in the first step, we subtract the carry, in accordance with the Add(Indexed) implementation(s) above. This is purely an implementation choice that has no impact on performance.
- Note
- Take care when using += (and -=) to add other KahanSums into a zero-initialized KahanSum. The operator behaves correctly in this case, but the result may be slightly off if you expect 0 + x to yield exactly x (where 0 is the zero-initialized KahanSum and x another KahanSum). In particular, x's carry term may get lost. This doesn't just happen with zero-initialized KahanSums; see the SubtractWithABitTooSmallCarry test case in the testKahan unittest for other examples. This behavior is internally consistent: the carry also gets lost if you switch the operands and it also happens with other KahanSum operators.
Definition at line 296 of file Util.h.
