Il modo migliore per riassumere un sacco di numeri in virgola mobile?

Question

Immaginate di avere una vasta gamma di numeri in virgola mobile, di tutti i tipi di formati. Qual è il modo più corretto per calcolare la somma, con il minimo errore? Ad esempio, quando la matrice è simile al seguente:

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

e si sommano da sinistra a destra con un semplice ciclo, come

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

ogni volta che si sommano i numeri più piccoli potrebbero scendere al di sotto della soglia di precisione in modo da l'errore diventa sempre più grande. Per quanto ne so il modo migliore è quello di ordinare l'array e iniziare ad aggiungere i numeri dal più basso al più alto, ma mi chiedo se c'è un modo ancora migliore (più veloce, più preciso)?

Modifica : Grazie per la risposta, ora ho un codice di lavoro che riassume perfettamente i valori doppi in Java. Si tratta di un porto direttamente dal posto di Python della risposta vincente. La soluzione passa tutti i miei test di unità. (Una versione più lunga, ma ottimizzata di questo è disponibile qui 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

Per "più precisa": questa ricetta in Python Cookbook ha algoritmi di sommatoria che mantengono la piena precisione (tenendo traccia dei totali parziali). Codice è in Python, ma anche se non si conosce Python è abbastanza chiaro per adattarsi a qualsiasi altra lingua.

Tutti i dettagli sono riportati nella questo documento .

Answer 2

Vedere anche: algoritmo somma Kahan Non richiede O (n) di stoccaggio, ma solo O (1).

Answer 3

Ci sono molti algoritmi, a seconda di ciò che si desidera. Di solito richiedono tenere traccia delle somme parziali. Se si mantiene solo l'indicazione degli importi x [k + 1] - x [k], si ottiene l'algoritmo Kahan. Se si tiene traccia di tutte le somme parziali (da cui cedimento O (n ^ 2) algoritmo), si ottiene la risposta s' @dF.

Si noti che in aggiunta al vostro problema, sommando il numero di diversi segni è molto problematico.

Ora, ci sono ricette semplici di tenere traccia di tutte le somme parziali:

• Ordina i numeri prima somma, sommare tutti i negativi e positivi anche separatamente. Se avete ordinato numeri, bene, altrimenti si ha O (n log n) algoritmo. Somma aumentando grandezza.
• Somma da coppie, quindi le coppie di coppie, ecc.

L'esperienza personale dimostra che di solito non è necessario cose più elaborato rispetto il metodo di Kahan.

Answer 4

Beh, se non si desidera ordinare, allora si può semplicemente mantenere il totale in una variabile con un tipo di precisione superiore a quello dei singoli valori (ad esempio, utilizzare un doppio per mantenere la somma dei carri, o di un "quad" per mantenere la somma di doppie). Ciò impone una penalizzazione delle prestazioni, ma potrebbe essere inferiore al costo di selezione.

Answer 5

Se l'applicazione si basa su ricerca di elaborazione numerica per una libreria di precisione aritmetica arbitraria, ma non so se ci sono librerie Python di questo tipo. Naturalmente, tutto dipende da quante cifre di precisione che si desidera -. Si possono ottenere buoni risultati con virgola mobile IEEE standard se lo si utilizza con cura