Wie berechnet man den Durchschnitt von Doppelpunkten, so dass der Gesamtfehler minimal ist?

Question

Angenommen, wir haben eine lange Reihe von Doppelpunkten, sagen wir N == 1000000.

array<double, N> arr; 

Es gibt zwei naive Ansätze, um den Durchschnitt zu berechnen. Erst

double result = 0; 
for (double x : arr) { 
    result += x; 
} 
result /= arr.size(); 

Dies kann ungenau sein, wenn die Summe der Werte sehr groß ist. Fließkommazahlen verlieren dann die Genauigkeit.

Ein weiterer Ansatz ist:

double result = 0; 
for (double x : arr) { 
    result += x/arr.size(); 
} 

Diese Genauigkeit verlieren kann, wenn die Zahlen klein sind.

Gibt es eine ausfallsichere Möglichkeit, einen einfachen Durchschnitt von Gleitkommazahlen zu berechnen? Lösungen, die nur die Standardbibliothek verwenden, werden geschätzt.

Answer 1

Wenn Sie mehr Genauigkeit aus dem Doppel drücken möchten, können Sie Kahan summation und schließlich die Division durch die Anzahl der Elemente verwenden. Es gibt jedoch keine Standardbibliotheksimplementierung von Kahans Summierung, die ich kenne.

Ein einfacher, standardmäßiger Weg (fast wie ein Betrug) wäre natürlich die Berechnung mit langen Doubles, im Grunde genommen mit Ihrer ersten Implementierung und nur mit der Konvertierung des Ergebnisses in doppelte Genauigkeit.

Answer 2

Eine Möglichkeit, den Genauigkeitsverlust zu reduzieren, wäre, die Doppel zu sortieren und dann in sortierter Reihenfolge zusammenzufassen, beginnend mit den kleinsten Werten und dann am Ende die Endsumme durch die Anzahl der Doppel zu teilen.

Also die Werkzeuge, die Sie benötigen, wäre std::sort und std::accumulate und plain alten Division /.

Answer 3

Die sogenannten naiven Wege sind nicht naiv. Was bedeuten die Daten und wie genau können Sie diese Werte messen? Wenn die Antwort nicht sehr ungewöhnlich ist, ist die einfache Methode mit Doppeln in Ordnung. Allerdings sind Schwimmer für den allgemeinen Gebrauch ein wenig unter Strom.

Wenn Sie die kleinen absoluten Werte zuerst hinzufügen, erhalten Sie möglicherweise ein zusätzliches Bit oder so. Das erfordert eine Art. Wenn die Daten alle über einem bestimmten Schwellenwert liegen, kann das Subtrahieren des Minimums auch ein anderes Bit ergeben.

Sie können auch eine partielle Summe und einen partiellen Mittelwert speichern und in jeder Phase überprüfen, ob die verarbeitete Teilmenge * innerhalb einer bestimmten Toleranz der Teilgesamtheit liegt. Das gibt Ihnen keine zusätzliche Genauigkeit, aber es wird Ihnen sagen, ob der FPU für Ihre Zwecke zu ungenau ist.

Sie können auch long double verwenden, oder sogar Ihre eigene Fließkomma-Bibliothek mit extended-precision codieren (oder die von jemand anderem benutzen). Die Lösungen werden jedoch zunehmend heroisch.