Kahan or Compensated Summation

Wikipedia describes this as follows:

In numerical analysis, the Kahan summation algorithm (also known as compensated summation [1]) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors).

Here are a couple of links (postscript document) which argue that this relatively simple method ought to be better known.

An Octave program to sum $s = x_1 + x_2 + ... + x_n$ is (embedded):

	function s = KahanSum(x)
	s = 0; % the sum
	r = 0; % the error or remainder
	for i = 1:length(x)
	tmp = s;
	y = x(i) + r;
	s = tmp + y; % s = s + x_i
	r = (tmp - s) + y;
	end
	end

view raw KahanSum.m hosted with ❤ by GitHub