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

StackOverflow https://stackoverflow.com/questions/394174

Question

Imaginez que vous avez un large éventail de nombres à virgule flottante, de toutes sortes de tailles. Quelle est la manière la plus correcte pour calculer la somme, avec la moindre 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 plus petits nombres pourraient tomber en dessous du seuil de précision si l'erreur devient de plus en plus. Pour autant que je sais que la meilleure façon est de trier le tableau et commencer à additionner des chiffres plus bas au plus haut, mais je me demande s'il y a une meilleure façon (plus rapide, plus précis)?

EDIT : Merci pour la réponse, j'ai maintenant un code de travail qui résume parfaitement les valeurs doubles en Java. Il est un port directement à partir du poste de Python de la réponse gagnante. La solution passe tous mes tests unitaires. (A plus longue, mais la version optimisée de c'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;
    }
}
Était-ce utile?

La solution

Pour « plus précis »: cette recette dans le livre de recettes Python a des algorithmes de sommation qui maintiennent la pleine précision (en gardant la trace des sous-totaux). Le code est en Python, mais même si vous ne savez pas Python, il est assez clair pour adapter à une autre langue.

Tous les détails sont donnés dans

Autres conseils

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

Il existe de nombreux algorithmes, en fonction de ce que vous voulez. Habituellement, ils exigent le suivi des sommes partielles. Si vous gardez seulement les sommes x [k + 1] - x [k], vous obtenez algorithme Kahan. Si vous gardez une trace de tous les (algorithme donc produisant O (n ^ 2)) sommes partielles, vous obtenez la réponse de @dF.

Notez que plus à votre problème, la somme des nombres de signes différents est très problématique.

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

  • Trier les chiffres avant de les additionner, la somme de toutes les négatifs et les points positifs indépendamment. Si vous avez réglé le nombre, bien, sinon vous avez O (n log n) algorithme. Somme en augmentant l'ampleur.
  • Somme par paires, puis paires de paires, etc.

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

Eh bien, si vous ne voulez pas trier alors vous pouvez simplement garder le total dans une variable avec un type de précision plus élevé que les valeurs individuelles (par exemple, utiliser un double pour maintenir la somme des flotteurs, ou un « quad » de garder la somme des doubles). Cela imposera une pénalité de performance, mais il pourrait être inférieur au coût du tri.

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top