La mejor manera de resumir una gran cantidad de números de punto flotante?

Question

Imagine que tiene una gran variedad de números de punto flotante, de todo tipo de tamaños. ¿Cuál es la forma más correcta para calcular la suma, con el mínimo error? Por ejemplo, cuando la matriz se ve así:

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

y se suman de izquierda a derecha con un bucle simple, como

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

cuando se suman los números más pequeños podrían caer por debajo del umbral de precisión por lo que el error se hace más grande y más grande. Por lo que yo sé la mejor manera es para ordenar la matriz y empezar a añadir los números de menor a mayor, pero me pregunto si hay una manera aún mejor (más rápido, más preciso)?

Editar : Gracias por la respuesta, ahora tengo un código de trabajo que resume a la perfección los valores dobles en Java. Es un puerto recta del poste del pitón de la respuesta ganadora. La solución pasa todas mis pruebas unitarias. (Una versión más larga pero optimizada de esta está disponible aquí 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

Para "más precisa": esta receta en el libro de cocina Python tiene algoritmos de suma que mantienen la precisión completa (por hacer el seguimiento de los subtotales). Es el código de Python, pero incluso si usted no sabe Python es lo suficientemente claro para adaptarse a cualquier otro idioma.

Todos los detalles se dan en la este documento .

Answer 2

Ver también: algoritmo de suma Kahan No requiere O (n) de almacenamiento, pero sólo O (1).

Answer 3

Hay muchos algoritmos, dependiendo de lo que desea. Por lo general, requieren hacer el seguimiento de las sumas parciales. Si se mantiene únicamente la indicación de los importes x [k + 1] - x [k], se obtiene el algoritmo Kahan. Si se mantiene un registro de todas las sumas parciales (de ahí dando O (n ^ 2) algoritmo), se obtiene respuesta @dF 's.

Tenga en cuenta que, además de su problema, sumando los números de diferentes signos es muy problemática.

Ahora, hay recetas simples que hacer el seguimiento de todas las sumas parciales:

• Ordenar los números antes de sumar, sumar todos los negativos y los aspectos positivos forma independiente. Si ha ordenado números, bien, de lo contrario tienes O (n log n) algoritmo. Suma mediante el aumento de magnitud.
• Sum por parejas, entonces pares de pares, etc.

La experiencia personal muestra que por lo general no necesita cosas más elegantes que el método de Kahan.

Answer 4

Bueno, si usted no desea ordenar entonces usted podría simplemente mantener el total en una variable con un tipo de una mayor precisión que los valores individuales (por ejemplo, usar una doble para mantener la suma de los flotadores, o un "quad" para mantener la suma de dobles). Esto impone una penalización de rendimiento, pero podría ser menor que el costo de la clasificación.

Answer 5

Si su aplicación se basa en la búsqueda de procesamiento numérico para una biblioteca de precisión aritmética arbitraria, sin embargo no sé si hay librerías de Python de este tipo. Por supuesto, todo depende de cuántos dígitos de precisión que desea -. Se puede lograr buenos resultados con coma flotante estándar IEEE si lo usa con cuidado