sum package:math-functions

Sum a collection of values. Example: foo = sum kbn [1,2,3]

Functions for summing floating point numbers more accurately than the naive sum function and its counterparts in the vector package and elsewhere. When used with floating point numbers, in the worst case, the sum function accumulates numeric error at a rate proportional to the number of values being summed. The algorithms in this module implement different methods of /compensated summation/, which reduce the accumulation of numeric error so that it either grows much more slowly than the number of inputs (e.g. logarithmically), or remains constant.

Calculate sum of series <math> Calculation is stopped when next value in series is less than ε·sum.

Calculate sum of series <math> Summation is stopped when <math> where ε is machine precision (m_epsilon)

O(n) Sum a vector of values.

A class for summation of floating point numbers.

Second-order Kahan-Babuška summation. This is more computationally costly than Kahan-Babuška-Neumaier summation, running at about a third the speed. Its advantage is that it can lose less precision (in admittedly obscure cases). This method compensates for error in both the sum and the first-order compensation term, hence the use of "second order" in the name.

Kahan-Babuška-Neumaier summation. This is a little more computationally costly than plain Kahan summation, but is always at least as accurate.

Kahan summation. This is the least accurate of the compensated summation methods. In practice, it only beats naive summation for inputs with large magnitude. Kahan summation can be less accurate than naive summation for small-magnitude inputs. This summation method is included for completeness. Its use is not recommended. In practice, KBNSum is both 30% faster and more accurate.

O(n) Sum a vector of values using pairwise summation. This approach is perhaps 10% faster than KBNSum, but has poorer bounds on its error growth. Instead of having roughly constant error regardless of the size of the input vector, in the worst case its accumulated error grows with O(log n).