Wie man am besten summieren viele Gleitkommazahlen?

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

Frage

Stellen Sie sich vor Sie haben eine große Palette von Gleitkommazahlen, aller Arten von Größen. Was ist der richtige Weg, um die Summe, mit dem geringsten Fehler zu berechnen? Wenn zum Beispiel das Array wie folgt aussieht: 

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

und fügen Sie von links nach rechts mit einer einfachen Schleife auf, wie 

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

, wenn Sie die kleineren Zahlen addieren sich möglicherweise unter der Präzision Schwelle fallen, so dass die Fehler größer und größer wird. Soweit ich die beste Art und Weise kenne, ist das Array zu sortieren und vom niedrigsten zum höchsten Aufsummierung Nummern beginnen, aber ich frage mich, ob es eine noch bessere Möglichkeit ist (schneller, präziser)?

Bearbeiten : Danke für die Antwort, habe ich jetzt einen funktionierenden Code haben, der perfekt doppelte Werte in Java fasst. Es ist ein gerade Port aus dem Python Beitrag der Sieger Antwort. Die Lösung geht alle meine Unit-Tests. (Eine längere, aber optimierte Version dieses hier ist 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;
    }
}
War es hilfreich?

Lösung

Für „präziser“: dieses Rezept in dem Python-Kochbuch Summen Algorithmen hat, die halte die volle Genauigkeit (durch den Überblick über die Zwischensummen zu halten). Code in Python ist aber auch wenn Sie Python nicht wissen, es ist klar genug, um eine andere Sprache anzupassen.

Alle werden die Details in

Andere Tipps

Siehe auch: Kahan Summenalgorithmus Dabei spielt es keine O erfordern (n) Speicher, sondern nur O (1).

Es gibt viele Algorithmen, je nachdem, was Sie wollen. Erfordern in der Regel halten sie den Überblick über die Teilsummen. Wenn Sie nur die halten die Summen x [k + 1] - x [k], erhalten Sie Kahan-Algorithmus. Wenn Sie den Überblick über alle Teilsummen halten (daher ergibt O (n ^ 2) Algorithmus), erhalten Sie @dF ‚s Antwort.

Beachten Sie, dass zusätzlich zu Ihrem Problem, Summieren Zahlen von verschiedenen Zeichen ist sehr problematisch.

Nun gibt es einfachere Rezepte als Überblick über alle Teilsummen zu halten:

  • Sortieren Sie die Zahlen vor Summieren summieren alle Negative und das Positive unabhängig voneinander. Wenn Sie Nummern sortiert haben, fein, sonst haben Sie O-Algorithmus (n log n). Summe von Größe zu erhöhen.
  • Summe von Paaren, dann Paare von Paaren, etc.

Die persönliche Erfahrung zeigt, dass Sie in der Regel brauchen nicht ausgefallenere Dinge als Kahan Methode.

Nun, wenn Sie nicht sortieren mögen, dann können Sie einfach die Gesamt halten in einer Variablen mit einer Art von höherer Genauigkeit als die einzelnen Werte (zB ein Doppel verwenden, um die Summe von Schwimmern zu halten, oder einen „Quad“ die Summe verdoppelt zu halten). Dies wird eine Leistungseinbuße verhängen, aber es könnte sein, weniger als die Kosten für die Sortierung.

Wenn Ihre Anwendung für eine beliebige Genauigkeit arithmetische Bibliothek auf numerische Verarbeitung Suche verlässt sich jedoch weiß ich nicht, ob es Python-Bibliotheken dieser Art sind. Natürlich hängt alles davon ab, wie viel Präzision Stellen Sie wollen -. Sie gute Ergebnisse mit Standard IEEE Floating-Point erreichen können, wenn man es mit Sorgfalt verwenden

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top