numpy/numpy — pull request #3685 by juliantaylor (2013-09-04 19:25:25+00:00)
Title: ENH: implement pairwise summation

pairwise summation has an average error of O(log(n)) instead of O(n) of
the regular summation.
It is implemented as summing pairs of small blocks of regulary summed
values in order to archive the same performance as the old sum.

An example of data which profits greatly is
d = np.ones500000)
(d / 10.).sum() - d.size / 10.

An alternative to pairwise summation is kahan summation but in order to
have a low performance penalty one must unroll and vectorize it,
while pairwise summation has the same speed without any vectorization.
The better error bound of O(1) is negligible in many cases.