How best to sum up lots of floating point numbers?

Question

Imagine you have a large array of floating point numbers, of all kinds of sizes. What is the most correct way to calculate the sum, with the least error? For example, when the array looks like this:

[1.0, 1e-10, 1e-10, ... 1e-10.0] 

and you add up from left to right with a simple loop, like

sum = 0 numbers.each do |val|     sum += val end 

whenever you add up the smaller numbers might fall below the precision threshold so the error gets bigger and bigger. As far as I know the best way is to sort the array and start adding up numbers from lowest to highest, but I am wondering if there is an even better way (faster, more precise)?

EDIT: Thanks for the answer, I now have a working code that perfectly sums up double values in Java. It is a straight port from the Python post of the winning answer. The solution passes all of my unit tests. (A longer but optimized version of this is available here Summarizer.java)

/**  * Adds up numbers in an array with perfect precision, and in O(n).  *   * @see http://code.activestate.com/recipes/393090/  */ public class Summarizer {      /**      * Perfectly sums up numbers, without rounding errors (if at all possible).      *       * @param values      *            The values to sum up.      * @return The sum.      */     public static double msum(double... values) {         List<Double> partials = new ArrayList<Double>();         for (double x : values) {             int i = 0;             for (double y : partials) {                 if (Math.abs(x) < Math.abs(y)) {                     double tmp = x;                     x = y;                     y = tmp;                 }                 double hi = x + y;                 double lo = y - (hi - x);                 if (lo != 0.0) {                     partials.set(i, lo);                     ++i;                 }                 x = hi;             }             if (i < partials.size()) {                 partials.set(i, x);                 partials.subList(i + 1, partials.size()).clear();             } else {                 partials.add(x);             }         }         return sum(partials);     }      /**      * Sums up the rest of the partial numbers which cannot be summed up without      * loss of precision.      */     public static double sum(Collection<Double> values) {         double s = 0.0;         for (Double d : values) {             s += d;         }         return s;     } } 

Answer 1

For "more precise": this recipe in the Python Cookbook has summation algorithms which keep the full precision (by keeping track of the subtotals). Code is in Python but even if you don't know Python it's clear enough to adapt to any other language.

All the details are given in this paper.

Answer 2

See also: Kahan summation algorithm It does not require O(n) storage but only O(1).