sums

Fast sumation functions.

Example:

static:
  block:
    const data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    doAssert sumKbn(data) == 45
    doAssert sumPairs(data) == 45

Funcs

func sumKbn[T](x: openArray[T]): T
Kahan-Babuška-Neumaier summation: O(1) error growth, at the expense of a considerable increase in computational expense.   Source Edit
func sumPairs[T](x: openArray[T]): T

Pairwise (cascade) summation of x[i0:i0+n-1], with O(log n) error growth (vs O(n) for a simple loop) with negligible performance cost if the base case is large enough.

See, e.g.:

In fact, the root-mean-square error growth, assuming random roundoff errors, is only O(sqrt(log n)), which is nearly indistinguishable from O(1) in practice. See:

  • Manfred Tasche and Hansmartin Zeuner, Handbook of Analytic-Computational Methods in Applied Mathematics (2000).
  Source Edit