La meilleure façon de résumer beaucoup de nombres à virgule flottante?

Question

Imaginez que vous avez un grand tableau de nombres flottants, de toutes sortes de tailles. Quelle est la plus correcte pour calculer la somme, avec le moins d'erreur? Par exemple, lorsque le tableau ressemble à ceci:

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

et vous ajoutez de gauche à droite avec une simple boucle, comme

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

chaque fois que vous ajoutez les petits nombres peuvent tomber au-dessous du seuil de précision afin que l'erreur devient de plus en plus gros. Autant que je sache, la meilleure façon est de trier le tableau et commencer à ajouter des numéros à partir de la plus basse à la plus haute, mais je me demande si il est encore mieux (plus rapide, plus précis)?

EDIT: Merci pour la réponse, j'ai maintenant un code de travail qui résume parfaitement le double des valeurs en Java. C'est un droit de port à partir de Python post de la bonne réponse. La solution passe tous mes tests unitaires. A plus long, mais la version optimisée de ce qui est disponible ici 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

Pour les "plus précis": cette recette dans le Python Cookbook a sommation des algorithmes qui permettent de garder toute la précision (en gardant la trace de la sous-totaux). Le Code est en Python, mais même si vous ne savez pas Python c'est assez clair pour s'adapter à une autre langue.

Tous les détails sont donnés dans le présent document.

Answer 2

Voir aussi: Kahan algorithme de sommation , Il ne nécessite pas de O(n) de stockage, mais seulement O(1).

Answer 3

Il existe de nombreux algorithmes, en fonction de ce que vous voulez. Habituellement, ils ont besoin de garder la trace des sommes partielles. Si vous ne garder que la somme x[k+1] - x[k], vous obtenez Kahan algorithme. Si vous gardez une trace de toutes les sommes partielles (et donc le rendement de O(n^2) algorithme de), vous obtenez @dF 's réponse.

Notez qu'en plus de votre problème, en additionnant les nombres de signes différents est très problématique.

Maintenant, il y a plus simple des recettes que de garder la trace de toutes les sommes partielles:

• Trier les nombres avant la sommation, la somme de tous les négatifs et les points positifs indépendamment. Si vous avez trié les numéros, amende, sinon vous avez O(n log n) de l'algorithme. Somme par l'augmentation de l'ampleur.
• Somme par paires, puis les paires de paires, etc.

L'expérience personnelle montre que vous n'avez généralement pas besoin de choses plus que Kahan de la méthode.

Answer 4

Eh bien, si vous ne voulez pas trier ensuite, vous pouvez simplement maintenir le total dans une variable avec un type d'une précision plus élevée que les valeurs individuelles (par exemple, utilisation d'un lit double pour garder la somme de flotteurs, ou d'un "quad" pour garder la somme des doubles). Cela imposera une pénalité sur les performances, mais il pourrait être moins cher que le coût de tri.

Answer 5

Si votre application s'appuie sur le traitement numérique de recherche pour une précision arbitraire de la bibliothèque, mais je ne sais pas si il y a des bibliothèques Python de ce genre. Bien sûr, tout dépend de combien de précision chiffres que vous voulez -- vous pouvez obtenir de bons résultats avec virgule flottante IEEE si vous l'utilisez avec soin.