Berechnen Sie das genaueste Ergebnis für: die Summe einer Liste von Fixpunkt-Nullnummern

Question

Nehmen wir an, Sie müssten einige 32-Bit-Festkommazahlen in einem riesigen Array L hinzufügen und Sie möchten die genaueste erhalten Ergebnis wie möglich. Darüber hinaus dürfen Sie nichts anderes als L und die 32-Bit-Festkommazahlen verwenden (d. H. Sie dürfen sie nicht in 64-Bit konvertieren). Was wäre Ihr Ansatz, um das genaueste Ergebnis für die Summe der Zahlen in L zu erhalten?

Dies würde mein aktueller Ansatz in sudo notierten Code:

L = sort(L) 
result = 0 
lastMax = false -- indicates whether we've extracted the maximum from L last time 

while (not empty(L)) and (result not equals +INF or -INF) do: 
    current = 0 
    if lastMax: 
    current = extractMin(L) -- gets and removes minimum from L 
    else: 
    current = extractMax(L) -- gets and removes maximum from L 
    result = safeAdd(result, current) 
    lastMax = not lastMax 

safeAdd(a,b): 
    if a = +INF: return +INF 
    else if a = -INF: return -INF 
    else: return a + b 

So zwischen dem Minimum/Maximum aus der verbleibenden Liste L, um mich abwechselnd Die Art und Weise zwischen den Bereichen von L. zu bleiben Wie safeAdd implementiert wird zeigt, dass, sobald wir die Genauigkeitsbereiche überschritten haben (dh das Ergebnis von 10 hat +INF oder -INF ergeben - so wie es in C getan wird) werden wir das Ergebnis nicht mehr ändern.

Haben Sie Vorschläge, wie Sie den Ansatz verbessern können?

Nebenbei bemerkt: Wir weiter davon aus, dass die + Betrieb ergeben können +INF oder -INF, die als Festpunktzahlen in der Programmiersprache dargestellt werden kann: Wenn wir sehr präzise sein wollen. Wir gehen jedoch davon aus, dass die Werte +INF, -INF nicht in L auftreten. Und wir ignorieren die Tatsache, dass der Fixpunktstandard auch eine Darstellung für NaN haben kann.

Answer 1

Wenn Sie wissen, dass das Ergebnis in Reichweite ist, müssen Sie sich nicht um Überlauf oder Unterlauf kümmern. Hier

ist ein Beispiel mit 4 Bits nur es einfach zu halten

7 0111 
+1 0001 
= 1000 <-- -8 overflow 
-1 0001 
= 0111 

Wenn Sie nicht sicher sind, wenn das Ergebnis in Reichweite ist, müssen Sie Über- bzw. Unterläufe zählen.

Für a = b + c

Überlauf, wenn b und c sind positiv und eine negativ

Unterschreitung, wenn b und c sind negativ und positiv