Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
ROOT::Math::KahanSum< T, N > Class Template Reference

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
TThe type of the values to be accumulated.
NNumber 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());
// or
k.Add(numbers);
The Kahan summation is a compensated summation algorithm, which significantly reduces numerical error...
Definition Util.h:122
void Add(T x)
Single-element accumulation. Will not vectorise.
Definition Util.h:165
double offset = 10.;
auto result = ROOT::Math::KahanSum<double, 4>::Accumulate(numbers.begin(), numbers.end(), offset);
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h offset
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t result
static KahanSum< T, N > Accumulate(Iterator begin, Iterator end, T initialValue=T{})
Iterate over a range and return an instance of a KahanSum.
Definition Util.h:211

Definition at line 122 of file Util.h.

Public Member Functions

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.
 
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, Noperator- ()
 
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
 
Result () const
 
Sum () const
 

Static Public Member Functions

template<class Iterator >
static KahanSum< T, NAccumulate (Iterator begin, Iterator end, T initialValue=T{})
 Iterate over a range and return an instance of a KahanSum.
 

Private Attributes

fCarry [N]
 
fSum [N]
 

#include <Math/Util.h>

Constructor & Destructor Documentation

◆ KahanSum() [1/4]

template<typename T = double, unsigned int N = 1>
ROOT::Math::KahanSum< T, N >::KahanSum ( initialValue = T{})
inlineexplicit

Initialise the sum.

Parameters
[in]initialValueInitialise with this value. Defaults to 0.

Definition at line 126 of file Util.h.

◆ KahanSum() [2/4]

template<typename T = double, unsigned int N = 1>
ROOT::Math::KahanSum< T, N >::KahanSum ( initialSumValue,
initialCarryValue 
)
inline

Initialise with a sum value and a carry value.

Parameters
[in]initialSumValueInitialise the sum with this value.
[in]initialCarryValueInitialise the carry with this value.

Definition at line 135 of file Util.h.

◆ KahanSum() [3/4]

template<typename T = double, unsigned int N = 1>
template<class Iterator >
ROOT::Math::KahanSum< T, N >::KahanSum ( Iterator  sumBegin,
Iterator  sumEnd,
Iterator  carryBegin,
Iterator  carryEnd 
)
inline

Initialise the sum with a pre-existing state.

Parameters
[in]sumBeginBegin of iterator range with values to initialise the sum with.
[in]sumEndEnd of iterator range with values to initialise the sum with.
[in]carryBeginBegin of iterator range with values to initialise the carry with.
[in]carryEndEnd of iterator range with values to initialise the carry with.

Definition at line 148 of file Util.h.

◆ KahanSum() [4/4]

template<typename T = double, unsigned int N = 1>
template<unsigned int M>
ROOT::Math::KahanSum< T, N >::KahanSum ( KahanSum< T, M > const &  other)
inline

Constructor to create a KahanSum from another KahanSum with a different number of accumulators.

Definition at line 157 of file Util.h.

Member Function Documentation

◆ Accumulate()

template<typename T = double, unsigned int N = 1>
template<class Iterator >
static KahanSum< T, N > ROOT::Math::KahanSum< T, N >::Accumulate ( Iterator  begin,
Iterator  end,
initialValue = T{} 
)
inlinestatic

Iterate over a range and return an instance of a KahanSum.

See Add(Iterator,Iterator) for details.

Parameters
[in]beginBeginning of a range.
[in]endEnd of the range.
[in]initialValueOptional initial value.

Definition at line 211 of file Util.h.

◆ Add() [1/3]

template<typename T = double, unsigned int N = 1>
template<class Container_t >
void ROOT::Math::KahanSum< T, N >::Add ( const Container_t &  inputs)
inline

Fill from a container that supports index access.

Parameters
[in]inputsContainer with index access such as std::vector or array.

Definition at line 195 of file Util.h.

◆ Add() [2/3]

template<typename T = double, unsigned int N = 1>
template<class Iterator >
void ROOT::Math::KahanSum< T, N >::Add ( Iterator  begin,
Iterator  end 
)
inline

Accumulate from a range denoted by iterators.

This function will auto-vectorise with random-access iterators.

Parameters
[in]beginBeginning of a range. Needs to be a random access iterator for automatic vectorisation, because a contiguous block of memory needs to be read.
[in]endEnd of the range.

Definition at line 180 of file Util.h.

◆ Add() [3/3]

template<typename T = double, unsigned int N = 1>
void ROOT::Math::KahanSum< T, N >::Add ( x)
inline

Single-element accumulation. Will not vectorise.

Definition at line 165 of file Util.h.

◆ AddIndexed()

template<typename T = double, unsigned int N = 1>
void ROOT::Math::KahanSum< T, N >::AddIndexed ( input,
std::size_t  index 
)
inline

Add input to the sum.

Particularly helpful when filling from a for loop. This function can be inlined and auto-vectorised if the index parameter is used to enumerate consecutive fills. Use Add() or Accumulate() when no index is available.

Parameters
[in]inputValue to accumulate.
[in]indexIndex of the value. Determines internal accumulator that this value is added to. Make sure that consecutive fills have consecutive indices to make a loop auto-vectorisable. The actual value of the index does not matter, as long as it is consecutive.

Definition at line 231 of file Util.h.

◆ Carry()

template<typename T = double, unsigned int N = 1>
T ROOT::Math::KahanSum< T, N >::Carry ( ) const
inline
Returns
The sum used for compensation.

Definition at line 250 of file Util.h.

◆ operator!=()

template<typename T = double, unsigned int N = 1>
template<typename U , unsigned int M>
bool ROOT::Math::KahanSum< T, N >::operator!= ( KahanSum< U, M > const &  other) const
inline

Definition at line 310 of file Util.h.

◆ operator+=() [1/2]

template<typename T = double, unsigned int N = 1>
template<typename U , unsigned int M>
KahanSum< T, N > & ROOT::Math::KahanSum< T, N >::operator+= ( const KahanSum< U, M > &  other)
inline

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 277 of file Util.h.

◆ operator+=() [2/2]

template<typename T = double, unsigned int N = 1>
KahanSum< T, N > & ROOT::Math::KahanSum< T, N >::operator+= ( arg)
inline

Add arg into accumulator. Does not vectorise.

Definition at line 255 of file Util.h.

◆ operator-()

template<typename T = double, unsigned int N = 1>
KahanSum< T, N > ROOT::Math::KahanSum< T, N >::operator- ( )
inline

Definition at line 299 of file Util.h.

◆ operator-=()

template<typename T = double, unsigned int N = 1>
template<typename U , unsigned int M>
KahanSum< T, N > & ROOT::Math::KahanSum< T, N >::operator-= ( KahanSum< U, M > const &  other)
inline

Subtract other KahanSum.

Does not vectorise.

Based on KahanIncrement from: Tian et al., 2012 (see operator+= documentation).

Definition at line 290 of file Util.h.

◆ operator==()

template<typename T = double, unsigned int N = 1>
template<typename U , unsigned int M>
bool ROOT::Math::KahanSum< T, N >::operator== ( KahanSum< U, M > const &  other) const
inline

Definition at line 305 of file Util.h.

◆ Result()

template<typename T = double, unsigned int N = 1>
T ROOT::Math::KahanSum< T, N >::Result ( ) const
inline
Returns
Compensated sum.

Definition at line 245 of file Util.h.

◆ Sum()

template<typename T = double, unsigned int N = 1>
T ROOT::Math::KahanSum< T, N >::Sum ( ) const
inline
Returns
Compensated sum.

Definition at line 240 of file Util.h.

Member Data Documentation

◆ fCarry

template<typename T = double, unsigned int N = 1>
T ROOT::Math::KahanSum< T, N >::fCarry[N]
private

Definition at line 316 of file Util.h.

◆ fSum

template<typename T = double, unsigned int N = 1>
T ROOT::Math::KahanSum< T, N >::fSum[N]
private

Definition at line 315 of file Util.h.

  • math/mathcore/inc/Math/Util.h