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

Immagina di avere una vasta gamma di numeri in virgola mobile, di tutti i tipi di dimensioni. Qual è il modo più corretto per calcolare la sum, con il minimo errore? Ad esempio, quando la matrice è simile a questa:

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

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

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

ogni volta che si sumno i numeri più piccoli potrebbero scendere al di sotto della soglia di precisione in modo che l’errore diventi sempre più grande. Per quanto ne so il modo migliore è quello di ordinare la matrice e iniziare a sumre i numeri dal più basso al più alto, ma mi chiedo se c’è un modo ancora migliore (più veloce, più preciso)?

EDIT : Grazie per la risposta, ora ho un codice funzionante che riassume perfettamente i doppi valori in Java. È una porta dritta dal post di Python della risposta vincente. La soluzione supera tutti i miei test unitari. (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 partials = new ArrayList(); 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 values) { double s = 0.0; for (Double d : values) { s += d; } return s; } } 

    Per “più preciso”: questa ricetta nel Cookbook Python ha algoritmi di sumtoria che mantengono la massima precisione (tenendo traccia dei subtotali). Il codice è in Python ma anche se non conosci Python è abbastanza chiaro per adattarsi a qualsiasi altra lingua.

    Tutti i dettagli sono riportati in questo documento .

    Vedi anche: Algoritmo di sumtoria di Kahan Non richiede la memorizzazione di O (n) ma solo O (1).

    Ci sono molti algoritmi, a seconda di ciò che vuoi. Di solito richiedono di tenere traccia delle somme parziali. Se mantieni solo le somme x [k + 1] – x [k], ottieni l’algoritmo di Kahan. Se si tiene traccia di tutte le somme parziali (da cui deriva l’algoritmo O (n ^ 2)), si ottiene la risposta di @dF.

    Nota che in aggiunta al tuo problema, sumre numeri di segni diversi è molto problematico.

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

    • Ordina i numeri prima della sum, sum tutti i negativi e i positivi in ​​modo indipendente. Se hai ordinato i numeri, bene, altrimenti hai l’algoritmo O (n log n). Somma aumentando la magnitudine.
    • Sommare a coppie, quindi coppie di coppie, ecc.

    L’esperienza personale dimostra che di solito non hai bisogno di cose più fantasiose del metodo di Kahan.

    Bene, se non vuoi ordinare, puoi semplicemente mantenere il totale in una variabile con un tipo di precisione maggiore rispetto ai singoli valori (es. Usare un doppio per mantenere la sum dei float o un “quad” per mantenere sum dei doppi). Questo imporrà una penalizzazione delle prestazioni, ma potrebbe essere inferiore al costo di smistamento.

    Se la tua applicazione si basa su una ricerca di elaborazione numerica per una libreria aritmetica di precisione arbitraria, tuttavia non so se ci sono librerie Python di questo tipo. Naturalmente, tutto dipende da quante cifre di precisione si desidera – è ansible ottenere buoni risultati con il virgola mobile IEEE standard se lo si utilizza con cura.