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();
}
 
ROOT::Math::KahanSum<double, 4> k;
k.Add(numbers.begin(), numbers.end());
// or
k.Add(numbers);

double offset = 10.;

auto result = ROOT::Math::KahanSum<double, 4>::Accumulate(numbers.begin(), numbers.end(), offset);

ROOT::Math::KahanSum::Accumulate

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:188

Definition at line 122 of file Util.h.

Public Member Functions
template<unsigned int M>
	KahanSum (KahanSum< T, M > const &other)
	Constructor to create a KahanSum from another KahanSum with a different number of accumulators. More...

	KahanSum (T initialValue=T{})
	Initialise the sum. More...

template<class Container_t >
void	Add (const Container_t &inputs)
	Fill from a container that supports index access. More...

template<class Iterator >
void	Add (Iterator begin, Iterator end)
	Accumulate from a range denoted by iterators. More...

void	Add (T x)
	Single-element accumulation. Will not vectorise. More...

void	AddIndexed (T input, std::size_t index)
	Add `input` to the sum. More...

T	Carry () const
	More...

	operator T () const
	Auto-convert to type T. More...

template<typename U >
KahanSum &	operator+= (const KahanSum< U > &arg)
	Add `arg` into accumulator. Does not vectorise. More...

KahanSum< T, N > &	operator+= (T arg)
	Add `arg` into accumulator. Does not vectorise. More...

KahanSum< T, N > &	operator-= (KahanSum< T, N > const &other)
	Subtract other KahanSum. More...

T	Result () const
	More...

T	Sum () const
	More...

Static Public Member Functions
template<class Iterator >
static KahanSum< T, N >	Accumulate (Iterator begin, Iterator end, T initialValue=T{})
	Iterate over a range and return an instance of a KahanSum. More...

Private Attributes
T	fCarry [N]
	More...

T	fSum [N]
	More...

#include <Math/Util.h>

Constructor & Destructor Documentation

◆ KahanSum() [1/2]

template<typename T = double, unsigned int N = 1>

ROOT::Math::KahanSum< T, N >::KahanSum ( T initialValue = T{} )

inline

Initialise the sum.

Parameters

[in] initialValue Initialise with this value. Defaults to 0.

Definition at line 126 of file Util.h.

◆ KahanSum() [2/2]

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 134 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,
		T	initialValue = `T{}`
	)

inlinestatic

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

See Add(Iterator,Iterator) for details.

Parameters

[in]	begin	Beginning of a range.
[in]	end	End of the range.
[in]	initialValue	Optional initial value.

Definition at line 188 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] inputs Container with index access such as std::vector or array.

Definition at line 172 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]	begin	Beginning of a range. Needs to be a random access iterator for automatic vectorisation, because a contiguous block of memory needs to be read.
[in]	end	End of the range.

Definition at line 157 of file Util.h.

◆ Add() [3/3]

template<typename T = double, unsigned int N = 1>

void ROOT::Math::KahanSum< T, N >::Add ( T x )

inline

Single-element accumulation. Will not vectorise.

Definition at line 142 of file Util.h.

◆ AddIndexed()

template<typename T = double, unsigned int N = 1>

void ROOT::Math::KahanSum< T, N >::AddIndexed	(	T	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]	input	Value to accumulate.
[in]	index	Index 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 208 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 232 of file Util.h.

◆ operator T()

template<typename T = double, unsigned int N = 1>

ROOT::Math::KahanSum< T, N >::operator T ( ) const

inline

Auto-convert to type T.

Definition at line 227 of file Util.h.

◆ operator+=() [1/2]

template<typename T = double, unsigned int N = 1>

template<typename U >

KahanSum& ROOT::Math::KahanSum< T, N >::operator+= ( const KahanSum< U > & arg )

inline

Add arg into accumulator. Does not vectorise.

Definition at line 244 of file Util.h.

◆ operator+=() [2/2]

template<typename T = double, unsigned int N = 1>

KahanSum<T, N>& ROOT::Math::KahanSum< T, N >::operator+= ( T arg )

inline

Add arg into accumulator. Does not vectorise.

Definition at line 237 of file Util.h.

◆ operator-=()

template<typename T = double, unsigned int N = 1>

KahanSum<T, N>& ROOT::Math::KahanSum< T, N >::operator-= ( KahanSum< T, N > const & other )

inline

Subtract other KahanSum.

Does not vectorise.

This is only meaningfull when both the sum and carry of each operand are of similar order of magnitude.

Definition at line 253 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 222 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 217 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 264 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 263 of file Util.h.

The documentation for this class was generated from the following file:

math/mathcore/inc/Math/Util.h

Auto-vectorisable accumulation

Examples

Public Member Functions

Static Public Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ KahanSum() [1/2]

◆ KahanSum() [2/2]

Member Function Documentation

◆ Accumulate()

◆ Add() [1/3]

◆ Add() [2/3]

◆ Add() [3/3]

◆ AddIndexed()

◆ Carry()

◆ operator T()

◆ operator+=() [1/2]

◆ operator+=() [2/2]

◆ operator-=()

◆ Result()

◆ Sum()

Member Data Documentation

◆ fCarry

◆ fSum