Beim (kaufmännischen) Runden einer Liste von Zahlen kann es dazu kommen, dass die Summe der gerundeten Zahlen nicht mehr der gerundeten Summe der ungerundeten Zahlen entspricht, wie folgendes Beispiel zeigt:
3.4 + 3.4 + 3.4 + 3.4 = 13.6 ≈ 14 3 + 3 + 3 + 3 = 12 ≠ 14
Rundungsfehler können sich also durch Addition soweit verstärken, dass in der Summe Abweichungen größer als 1 entstehen können. Um dieses Problem zu vermeiden, kann man folgendermaßen vorgehen: Nachdem zunächst alle Zahlen abgerundet wurden, muss man solange, wie die Summe der gerundeten Zahlen noch nicht der gerundeten Summe der ungerunderen Zahlen entspricht, die jeweilige Zahl, deren Differenz zur entsprechenden ungerundeten Zahl noch am am größten ist, um 1 erhöhen. Es folgt ein Beispiel:
10.3 + 11.2 + 15.4 + 20.2 + 50.6 = 107.7 ≈ 108 10 + 11 + 15 + 20 + 50 = 106 ≠ 108 (alle Zahlen abgerundet) 10 + 11 + 15 + 20 + 51 = 107 ≠ 108 (50 um 1 auf 51 erhöht, weil 50.6 − 50 die größte Differenz ist) 10 + 11 + 16 + 20 + 51 = 108 = 108 (15 um 1 auf 16 erhöht, weil 15.4 − 15 die größte Differenz ist)
Die Zahlen 10.3, 11.2, 15.4, 20.2 und 50.6 werden also zu 10, 11, 16, 20 und 51 gerundet. Nicht jede Zahl ist kaufmännisch gerundet worden, sondern so auf- oder abgerundet worden, dass die Gesamtsumme der gerundeten Zahlen der kaufmännisch gerundeten Summe der ungerundeten Zahlen entspricht, und der maximale absolute Rundungsfehler jeder einzelnen gerundeten Zahl so klein wie möglich ist. Um das Verfahren eindeutig zu gestalten, wird im Falle von mehreren gleich großen Differenzen jene gerundete Zahl erhöht, die selbst am größten ist. (In der vorherigen Version dieses Dokumentes wurde die kleinste Zahl verwendet.) Gibt es mehrere gleiche kleinste Zahlen, die die größten Differenzen zu den dazugehörigen ungerundeten Zahlen aufweisen, wird im Falle eines positiven Vorzeichens der dazugehörigen ungerundeten Zahlen die erstmögliche Zahl erhöht, und im Falle eines negativen Vorzeichens die letztmögliche Zahl erhöht. Durch diese Regelungen ist das Verfahren soweit wie möglich von der Sortierung der Zahlen unabhängig und weiterhin invariant gegen einen Austausch aller Vorzeichen, wie die folgenden Beispiele zeigen:
10.4 + 11.2 + 15.3 + 20.4 + 50.6 = 107.9 ≈ 108
10 + 11 + 15 + 20 + 50 = 106 ≠ 108 (alle Zahlen abgerundet)
10 + 11 + 15 + 20 + 51 = 107 ≠ 108 (50 um 1 auf 51 erhöht, weil 50.6 − 50 die größte Differenz ist)
10 + 11 + 15 + 21 + 51 = 108 = 108 (20 um 1 auf 21 erhöht,
weil 20.4 − 20 und 10.4 − 10 die größten Differenzen sind,
und 20.4 größer als 10.4 ist)
20.4 + 11.2 + 15.3 + 10.4 + 50.6 = 107.9 ≈ 108
20 + 11 + 15 + 10 + 50 = 106 ≠ 108 (alle Zahlen abgerundet)
20 + 11 + 15 + 10 + 51 = 107 ≠ 108 (50 um 1 auf 51 erhöht, weil 50.6 − 50 die größte Differenz ist)
21 + 11 + 15 + 10 + 51 = 108 = 108 (20 um 1 auf 21 erhöht,
weil 20.4 − 20 und 10.4 − 10 die größten Differenzen sind,
und 20.4 größer als 10.4 ist)
(−20.6) + 10.4 + 10.4 = 0.2 ≈ 0
(−21) + 10 + 10 = (−1) ≠ 0 (alle Zahlen abgerundet)
(−21) + 11 + 10 = 1 = 0 (linke 10 um 1 auf 11 erhöht, weil alle Differenzen gleich sind,
10.4 größer als −20.6 ist und 10.4 positiv ist)
20.6 + (−10.4) + (−10.4) = (−0.2) ≈ 0
20 + (−11) + (−11) = (−2) ≠ 0 (alle Zahlen abgerundet)
21 + (−11) + (−11) = (−1) ≠ 0 (20 um 1 auf 21 erhöht, da Differenzen gleich und 20.6 größer als −10.4)
21 + (−11) + (−10) = 0 = 0 (rechte −11 um 1 auf −10 erhöht, da Differenzen gleich und −10.4 negativ)
Diesen Algorithmus kann man so erweitern, dass er auf Baumstrukturen anwendbar ist bzw. ineinander verschachtelte Teilsummen berücksichtigen kann, so dass diese beim Addieren der gerundeten Werte eine Abweichung aufweisen, die stets kleiner als 1 ist. Hierzu geht man wie folgt vor: Die Gesamtsumme wird zunächst kaufmännisch gerundet. Anschließend wird der oben beschriebene Algorithmus verwendet, um die Teilsummen der obersten Ebene zu runden. Für jede Teilsumme die ihrerseits wieder aus Teilsummen oder Teilbeträgen besteht, wird der Algorithmus erneut angewendet, jedoch nicht mit kaufmännischer Rundung der Teilsumme, sondern unter Verwendung des bereits erlangten Rundungsergebnisses für diese Teilsumme.
Ich habe diesen Algorithmus in einfacher Form, sowie in der Form für Baumstrukturen bzw. Teilsummen in einem Haskell-Programm (tree-round.hs) implementiert. Einige Demonstrations-Berechnungen des Programmes folgen:
[206497/2730 ~= 75.64 -> 76] | +- [201947/2730 ~= 73.97 -> 74] | | | +- [29/3 ~= 9.67 -> 9] | | | +- [169/10 ~= 16.90 -> 17] | | | | | +- [1179/10 ~= 117.90 -> 118] | | | | | `- [-101 -> -101] | | | +- [48/13 ~= 3.69 -> 4] | | | `- [306/7 ~= 43.71 -> 44] | `- [5/3 ~= 1.67 -> 2] [124093/2380 ~= 52.14 -> 52] | +- [215/17 ~= 12.65 -> 13] | +- [44087/840 ~= 52.48 -> 52] | | | +- [372/7 ~= 53.14 -> 53] | | | `- [-79/120 ~= -0.66 -> -1] | | | +- [-61/5 ~= -12.20 -> -12] | | | `- [277/24 ~= 11.54 -> 11] | `- [-1559/120 ~= -12.99 -> -13] | +- [-493/24 ~= -20.54 -> -21] | +- [-156/5 ~= -31.20 -> -31] | +- [389/10 ~= 38.90 -> 39] | `- [-3/20 ~= -0.15 -> 0] [2718/5 ~= 543.60 -> 544] | +- [666/5 ~= 133.20 -> 133] | | | +- [333/10 ~= 33.30 -> 34] | | | +- [333/10 ~= 33.30 -> 33] | | | +- [333/10 ~= 33.30 -> 33] | | | `- [333/10 ~= 33.30 -> 33] | `- [2052/5 ~= 410.40 -> 411] | +- [513/5 ~= 102.60 -> 103] | +- [513/5 ~= 102.60 -> 103] | +- [513/5 ~= 102.60 -> 103] | `- [513/5 ~= 102.60 -> 102]
Der gerundete Wert jedes Knotens entspricht jeweils exakt der Summe aller gerundeten Werte seiner direkten Unterknoten. Ganzzahlen werden nicht modifizert, Bruchzahlen werden entweder auf- oder abgerundet. Nur für die Wurzel des Baumes ist eine kaufmännische Rundung garantiert.
Urheber: Jan Behrens (2008-2009)
Es wird unentgeltlich jeder Person das Recht eingeräumt, Kopien dieses Dokumentes und des dazugehörigen Haskell-Programmes zu benutzen, zu kopieren, zu modifizieren, mit anderen Werken zu kombinieren, zu veröffentlichen, zu verbreiten, unterzulizensieren, zu verkaufen und/oder weiteren Personen diese Rechte einzuräumen, soweit in allen Kopien oder wesentlichen Teilen davon der Autor genannt wird und dieser Hinweistext enthalten ist. Fehlerfreiheit und Eignung für einen bestimmten Zweck werden nicht zugesichert; Verwendung erfolgt auf eigenes Risiko.