2Summe - 2Sum

2Sum ist ein Gleitkomma- Algorithmus zum Berechnen des exakten Rundungsfehlers in einer Gleitkomma-Additionsoperation.

2Sum und seine Variante Fast2Sum wurden erstmals 1965 von Møller veröffentlicht. Fast2Sum wird oft implizit in anderen Algorithmen wie kompensierten Summationsalgorithmen verwendet ; Kahans Summationsalgorithmus wurde zuerst 1965 veröffentlicht und Fast2Sum wurde später von Dekker 1971 für Doppel-Doppel-Arithmetik- Algorithmen herausgerechnet. Die Namen 2Sum und Fast2Sum scheinen 1997 von Shewchuk rückwirkend angewendet worden zu sein.

Algorithmus

Bei zwei Gleitkommazahlen und berechnet 2Sum die Gleitkommasumme und den Gleitkommafehler, sodass . Der Fehler ist selbst eine Gleitkommazahl. ${\displaystyle a}$${\displaystyle b}$${\displaystyle s:=\operatorname {fl} (a+b)}$${\displaystyle t:=a+b-\operatorname {fl} (a+b)}$${\displaystyle s+t=a+b}$${\displaystyle t}$

Gibt Gleitkommazahlen ein${\displaystyle a,b}$

Gibt Summe und Fehler aus${\displaystyle s=\operatorname {fl} (a+b)}$${\displaystyle t=a+b-\operatorname {fl} (a+b)}$

1. ${\displaystyle s:=a\oplus b}$
2. ${\displaystyle a':=s\ominus b}$
3. ${\displaystyle b':=s\ominus a'}$
4. ${\displaystyle \delta_{a}:=a\ominus a'}$
5. ${\displaystyle \delta_{b}:=b\ominus b'}$
6. ${\displaystyle t:=\delta_{a}\oplus\delta_{b}}$
7. Rückkehr ${\displaystyle (s,t)}$

Vorausgesetzt, dass die Gleitkomma-Arithmetik korrekt auf den nächsten Wert gerundet ist (mit beliebig aufgelösten Verbindungen), wie dies der Standard in IEEE 754 ist , und vorausgesetzt, dass die Summe nicht überläuft und, wenn sie unterschreitet, allmählich unterläuft , kann nachgewiesen werden, dass .${\displaystyle s+t=a+b}$

Eine Variante von 2Sum namens Fast2Sum verwendet nur drei Gleitkomma-Operationen für Gleitkomma-Arithmetik in Radix 2 oder Radix 3, unter der Annahme, dass der Exponent von mindestens so groß ist wie der Exponent von , z. B. wenn :${\displaystyle a}$${\displaystyle b}$${\displaystyle \left|a\right|\geq \left|b\right|}$

Eingabe von Radix-2- oder Radix-3-Gleitkommazahlen und , von denen mindestens eine Null ist oder die jeweils normierte Exponenten haben${\displaystyle a}$${\displaystyle b}$${\displaystyle e_{a}\geq e_{b}}$

Gibt Summe und Fehler aus${\displaystyle s=\operatorname {fl} (a+b)}$${\displaystyle t=a+b-\operatorname {fl} (a+b)}$

1. ${\displaystyle s:=a\oplus b}$
2. ${\displaystyle z=s\ominus a}$
3. ${\displaystyle t=b\ominus z}$
4. Rückkehr ${\displaystyle (s,t)}$

Selbst wenn die Bedingungen nicht erfüllt sind, liefern 2Sum und Fast2Sum oft vernünftige Näherungen für den Fehler, so dass Algorithmen für kompensierte Summation, Punktprodukt usw ist ungewöhnlich. Kompliziertere Varianten von 2Sum und Fast2Sum gibt es auch für andere Rundungsmodi als Runden auf Nächstes. ${\displaystyle s+t\approx a+b}$

Siehe auch

• Kahan-Summierungsalgorithmus
• Rundungsfehler
• Doppel-Doppel-Arithmetik

Verweise