Welcher Algorithmus ist genauer, um die Summe eines sortierten Arrays von Zahlen zu berechnen?

Gegeben ist eine zunehmende endliche Folge von positiven Zahlen . Welcher der beiden folgenden Algorithmen ist besser für die Berechnung der Summe der Zahlen?$z_{1} ,z_{2},.....z_{n}$

s=0; 
for \ i=1:n 
    s=s + z_{i} ; 
end

Oder:

s=0; 
for \ i=1:n 
s=s + z_{n-i+1} ; 
end

Meiner Meinung nach ist es besser, die Zahlen von der größten zur kleinsten Zahl zu addieren, da der Fehler immer kleiner wird. Wir wissen auch, dass, wenn wir einer sehr kleinen Zahl eine sehr große Zahl hinzufügen, das ungefähre Ergebnis die große Zahl sein kann.

Ist das richtig? Was kann man noch sagen?

Das Addieren beliebiger Gleitkommazahlen ergibt normalerweise einen Rundungsfehler, und der Rundungsfehler ist proportional zur Größe des Ergebnisses. Wenn Sie eine einzelne Summe berechnen und zuerst die größten Zahlen addieren, ist das durchschnittliche Ergebnis größer. Sie würden also mit den kleinsten Zahlen beginnen.

Sie erhalten jedoch ein besseres Ergebnis (und es wird schneller ausgeführt), wenn Sie beispielsweise vier Summen erzeugen: Beginnen Sie mit sum1, sum2, sum3, sum4 und fügen Sie vier Array-Elemente nacheinander zu sum1, sum2, sum3, sum4 hinzu. Da jedes Ergebnis im Durchschnitt nur 1/4 der ursprünglichen Summe beträgt, ist Ihr Fehler viermal kleiner.

Besser noch: Addiere die Zahlen paarweise. Dann addieren Sie die Ergebnisse paarweise. Addieren Sie diese Ergebnisse erneut paarweise und so weiter, bis Sie nur noch zwei Zahlen zum Hinzufügen haben.

Ganz einfach: Höhere Präzision verwenden. Verwenden Sie long double, um eine Summe von Doubles zu berechnen. Verwenden Sie double, um die Summe der Floats zu berechnen.

Nahezu perfekt: Schlagen Sie den oben beschriebenen Kahan-Algorithmus nach. Am besten noch mit der kleinsten Zahl beginnend addieren.

Sind das ganze Zahlen oder Gleitkommazahlen? Angenommen, es ist Gleitkomma, würde ich mit der ersten Option gehen. Es ist besser, die kleineren Zahlen miteinander zu addieren, als die größeren Zahlen später. Mit der zweiten Option werden Sie am Zusatz einer geringen Anzahl an eine große Anzahl als Ende i erhöht, was zu Problemen führen kann. Hier ist eine gute Quelle für Fließkommaarithmetik: Was jeder Informatiker über Fließkommaarithmetik wissen sollte

animal_magics Antwort ist richtig, dass Sie die Zahlen vom kleinsten zum größten addieren sollten, aber ich möchte ein Beispiel geben, um zu zeigen, warum.

Angenommen, wir arbeiten in einem Gleitkommaformat, das uns eine erstaunliche Genauigkeit von 3 Stellen bietet. Nun wollen wir zehn Zahlen hinzufügen:

[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Natürlich ist die genaue Antwort 1009, aber wir können das nicht in unserem 3-stelligen Format bekommen. Die genaueste Antwort, die wir bekommen, ist 1010, auf 3 Stellen gerundet. Wenn wir die kleinste zur größten addieren, bekommen wir auf jeder Schleife:

Loop Index        s
1                 1
2                 2
3                 3
4                 4
5                 5
6                 6
7                 7
8                 8
9                 9
10                1009 -> 1010

So erhalten wir die genauestmögliche Antwort für unser Format. Nehmen wir nun an, wir addieren vom größten zum kleinsten.

Loop Index        s
1                 1000
2                 1001 -> 1000
3                 1001 -> 1000
4                 1001 -> 1000
5                 1001 -> 1000
6                 1001 -> 1000
7                 1001 -> 1000
8                 1001 -> 1000
9                 1001 -> 1000
10                1001 -> 1000

Da die Gleitkommazahlen nach jeder Operation gerundet werden, werden alle Additionen abgerundet, wodurch sich unser Fehler von 1 auf 9 genau erhöht. Stellen Sie sich nun vor, Ihre hinzuzufügende Zahlenreihe hätte 1000 und dann hundert Einsen oder eine Million. Beachten Sie, dass Sie, um wirklich genau zu sein, die kleinsten zwei Zahlen summieren und dann das Ergebnis in Ihre Zahlenmenge umwandeln möchten.

Für den allgemeinen Fall würde ich eine kompensierte Summation (oder Kahan-Summation) verwenden. Wenn die Nummern nicht bereits sortiert sind, ist das Sortieren viel teurer als das Hinzufügen . Kompensierte Summation ist auch genauer als sortierte Summation oder naive Summation (siehe den vorherigen Link).

Zu den Referenzen: Was jeder Programmierer über Gleitkommaarithmetik wissen sollte, behandelt die Grundpunkte so detailliert, dass jemand sie in 20 (+/- 10) Minuten lesen und die Grundlagen verstehen kann. "Was jeder Informatiker über Fließkommaarithmetik wissen sollte" von Goldberg ist die klassische Referenz, aber die meisten Leute, die ich kenne, empfehlen, dass das Papier nicht im Detail gelesen wird, weil es ungefähr 50 Seiten umfasst (in einigen Fällen mehr als das) Drucke) und in dichter Prosa geschrieben, so habe ich Probleme, dies als erste Referenz für Menschen zu empfehlen. Es ist gut für einen zweiten Blick auf das Thema. Eine enzyklopädische Referenz ist Highams Genauigkeit und Stabilität numerischer Algorithmen, die dieses Material sowie die Anhäufung von numerischen Fehlern in vielen anderen Algorithmen abdeckt; Es sind auch 680 Seiten, daher würde ich mir diese Referenz auch nicht zuerst ansehen.

Die vorherigen Antworten behandeln die Angelegenheit bereits allgemein und geben fundierte Ratschläge, aber es gibt noch eine weitere Besonderheit, die ich erwähnen möchte. Auf den meisten modernen Architekturen würde die von forIhnen beschriebene Schleife ohnehin mit einer erweiterten Genauigkeit von 80 Bit ausgeführt , was eine zusätzliche Genauigkeit garantiert, da alle temporären Variablen in Registern abgelegt werden. Sie haben also bereits eine Art Schutz vor numerischen Fehlern. In komplizierteren Schleifen werden die Zwischenwerte jedoch zwischen den Operationen im Speicher gespeichert und daher auf 64 Bit gekürzt. Ich vermute, dass

s=0; 
for \ i=1:n 
    printf("Hello World");
    s=s + z_{i} ; 
end

Dies reicht aus, um eine geringere Genauigkeit in der Summierung zu erzielen (!!). Seien Sie also sehr vorsichtig, wenn Sie Ihren Code drucken und debuggen möchten, während Sie die Richtigkeit überprüfen.

Für die Interessierten beschreibt dieser Aufsatz ein Problem in einer weit verbreiteten numerischen Routine (Lapacks rangaufschlussreiche QR-Faktorisierung), deren Debugging und Analyse gerade aufgrund dieses Problems sehr schwierig war.

Von den beiden Optionen führt das Hinzufügen von kleiner zu größer zu weniger numerischen Fehlern als das Hinzufügen von größer zu kleiner.

Vor> 20 Jahren in meiner Klasse "Numerische Methoden" gab der Ausbilder dies jedoch an und mir fiel auf, dass dies immer noch mehr Fehler verursachte als notwendig, da der relative Wertunterschied zwischen dem Akkumulator und den hinzugefügten Werten bestand.

Eine logische Lösung besteht darin, die 2 kleinsten Zahlen in die Liste einzufügen und den summierten Wert erneut in die sortierte Liste einzufügen.

Um dies zu demonstrieren, habe ich einen Algorithmus entwickelt, der dies effizient (räumlich und zeitlich) durchführen kann, indem der freiwerdende Speicherplatz verwendet wird, wenn Elemente aus dem primären Array entfernt werden, um ein sekundäres Array der seit den Additionen inhärent geordneten summierten Werte zu erstellen waren von der Summe der Werte, die immer größer wurden. Bei jeder Iteration werden dann die "Spitzen" beider Arrays überprüft, um die 2 kleinsten Werte zu finden.

Da Sie den zu verwendenden Datentyp nicht eingeschränkt haben, verwenden Sie einfach Zahlen mit beliebiger Länge, um ein perfektes Ergebnis zu erzielen. In diesem Fall spielt die Reihenfolge keine Rolle. Es wird viel langsamer sein, aber Perfektion zu erreichen, braucht Zeit.

Verwenden Sie die Binärbaumaddition, dh wählen Sie den Mittelwert der Verteilung (nächste Zahl) als Wurzel des Binärbaums und erstellen Sie einen sortierten Binärbaum, indem Sie links im Diagramm kleinere und rechts größere Werte usw. hinzufügen . Das rekursive Hinzufügen aller untergeordneten Knoten eines einzelnen übergeordneten Knotens in einem Bottom-Up-Ansatz. Dies ist effizient, da der durchschnittliche Fehler mit der Anzahl der Summierungen zunimmt, und in einem Binärbaumansatz liegt die Anzahl der Summierungen in der Größenordnung von log n in der Basis 2. Daher wäre der durchschnittliche Fehler geringer.

Was Hristo Iliev oben über 64-Bit-Compiler gesagt hat, die die SSE- und AVX-Anweisungen gegenüber der FPU (AKA NDP) bevorzugen, ist zumindest für Microsoft Visual Studio 2013 absolut richtig Es ist tatsächlich schneller und theoretisch auch genauer, die FPU zu verwenden. Wenn es Ihnen wichtig ist, würde ich vorschlagen, zuerst verschiedene Lösungen zu testen, bevor Sie sich für einen endgültigen Ansatz entscheiden.

Wenn ich in Java arbeite, verwende ich sehr häufig den BigDecimal-Datentyp mit willkürlicher Genauigkeit. Es ist einfach zu einfach und man merkt normalerweise nicht, dass die Geschwindigkeit abnimmt. Das Berechnen der transzendentalen Funktionen mit unendlichen Reihen und sqrt nach der Newton-Methode kann eine Millisekunde oder länger dauern, ist aber machbar und ziemlich genau.

Ich habe dies nur hier gelassen /programming//a/58006104/860099 (wenn Sie dorthin gehen, klicken Sie auf "Code-Snippet anzeigen" und führen Sie es über die Schaltfläche aus

Es ist ein JavaScript-Beispiel, das deutlich zeigt, dass die Summe ab dem größten Fehler größer ist

arr=[9,.6,.1,.1,.1,.1];

sum     =             arr.reduce((a,c)=>a+c,0);  // =  9.999999999999998
sortSum = [...arr].sort().reduce((a,c)=>a+c,0);  // = 10

console.log('sum:     ',sum);
console.log('sortSum:',sortSum);