algorithm - que - punto flotante plc

¿Cuál es la mejor manera de resumir muchos números de coma flotante?

Question

Imagine que tiene una gran variedad de números de coma flotante, de todo tipo de tamaños. ¿Cuál es la forma más correcta de 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 simple bucle, como

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

cada vez que suma los números más pequeños pueden caer por debajo del umbral de precisión, por lo que el error aumenta y aumenta. Por lo que yo sé, la mejor manera es ordenar la matriz y comenzar a sumar los números de menor a mayor, pero me pregunto si hay una forma mejor (más rápida, más precisa).

EDITAR : Gracias por la respuesta, ahora tengo un código de trabajo que resume perfectamente los valores dobles en Java. Es un puerto directo desde la publicación de Python de la respuesta ganadora. La solución pasa todas las pruebas de mi unidad. (Una versión más larga pero optimizada de esto 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

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

Answer 2

Si su aplicación se basa en la búsqueda de procesamiento numérico para una biblioteca aritmética de precisión arbitraria, no sé si hay bibliotecas de Python de este tipo. Por supuesto, todo depende de la cantidad de dígitos de precisión que desee; puede lograr buenos resultados con el punto flotante IEEE estándar si lo usa con cuidado.

Answer 3

Ver también: Algoritmo de suma de Kahan No requiere O (n) almacenamiento sino solo O (1).

Answer 4

Hay muchos algoritmos, dependiendo de lo que quieras. Por lo general, requieren un seguimiento de las sumas parciales. Si solo conservas las sumas x [k + 1] - x [k], obtienes el algoritmo de Kahan. Si realiza un seguimiento de todas las sumas parciales (lo que arroja un algoritmo O (n ^ 2)), obtiene la respuesta de @dF.

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

Ahora, hay recetas más simples que hacer un seguimiento de todas las sumas parciales:

• Ordene los números antes de sumar, sume todos los negativos y los positivos de forma independiente. Si tiene números ordenados, está bien; de lo contrario, tiene el algoritmo O (n log n). Suma al aumentar la magnitud.
• Suma por pares, luego pares de pares, etc.

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

Answer 5

Para "más preciso": esta receta en el Python Cookbook tiene algoritmos de suma que mantienen la precisión total (al hacer un seguimiento de los subtotales). El código está en Python, pero incluso si no conoces Python, es lo suficientemente claro como para adaptarse a cualquier otro idioma.

Todos los detalles se dan en este documento .