Useful algorithms from the journey

This page lists all the algorithms I found and don't wish to forget. This is a collection of algorithms, and I make no claim of invention.

Kahan's summation formula

Original source: See theorem 8

Code:

def sum(array):
  result    = 0  # the partial sums
  underflow = 0  # the error that accumulates
  for x in array:
    y   = x - underflow  # accumulate previous k least significant bits
    tmp = result + y     # temporary sum. k least significant bits are lost
    underflow = (tmp - result) - y  # recover k least significant bits
    result = tmp         # now we can use the previously computed sum
  return result          # the last few least sign. bits are unrecoverable

This algorithm provides a much tighter error, bound by 2nε, instead of 2n²ε that is the result of a simple summation algorithm.