View source for 2Sum

{{short description|Algorithm to compute rounding error}}
'''2Sum'''<ref name="handbook">{{cite book
|last1=Muller
|first1=Jean-Michel
|last2=Brunie
|first2=Nicolas
|last3=de Dinechin
|first3=Florent
|last4=Jeannerod
|first4=Claude-Pierre
|last5=Joldes
|first5=Mioara
|last6=Lefèvre
|first6=Vincent
|last7=Melquiond
|first7=Guillaume
|last8=Revol
|first8=Nathalie
|author8-link=Nathalie Revol
|last9=Torres
|first9=Serge
|title=Handbook of Floating-Point Arithmetic
|date=2018
|publisher=Birkhäuser
|location=Cham, Switzerland
|isbn=978-3-319-76525-9
|pages=104–111
|doi=10.1007/978-3-319-76526-6
|edition=2nd
|url=https://doi.org/10.1007/978-3-319-76526-6
|access-date=2020-09-20
|archive-date=2023-04-28
|archive-url=https://web.archive.org/web/20230428173828/https://link.springer.com/book/10.1007/978-3-319-76526-6
|url-status=live
}}</ref> is a [[Floating-point arithmetic|floating-point]] algorithm for computing the exact [[round-off error]] in a floating-point addition operation.

2Sum and its variant Fast2Sum were first published by Ole Møller in 1965.<ref name="moeller">{{cite journal
|last1=Møller
|first1=Ole
|title=Quasi double-precision in floating point addition
|journal=BIT Numerical Mathematics
|date=March 1965
|volume=5
|pages=37–50
|doi=10.1007/BF01975722
|s2cid=119991676
}}</ref>
Fast2Sum is often used implicitly in other algorithms such as [[Kahan summation algorithm|compensated summation algorithms]];<ref name="handbook"/> Kahan's summation algorithm was published first in 1965,<ref name="kahan">{{cite journal
|last1=Kahan
|first1=W.
|author-link=William Kahan
|title=Further remarks on reducing truncation errors
|journal=Communications of the ACM
|date=January 1965
|volume=8
|issue=1
|page=40
|doi=10.1145/363707.363723
|publisher=Association for Computing Machinery
|s2cid=22584810
|issn=0001-0782
|doi-access=free
}}</ref> and Fast2Sum was later factored out of it by [[Theodorus Dekker|Dekker]] in 1971 for [[double-double arithmetic]] algorithms.<ref name="dekker"/>
The names ''2Sum'' and ''Fast2Sum'' appear to have been applied retroactively by Shewchuk in 1997.<ref name="shewchuk">{{cite journal
|last1=Shewchuk
|first1=Jonathan Richard
|title=Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates
|journal=[[Discrete & Computational Geometry]]
|date=October 1997
|volume=18
|issue=3
|pages=305–363
|doi=10.1007/PL00009321
|doi-access=free
}}</ref>

== Algorithm ==

Given two floating-point numbers <math>a</math> and <math>b</math>, 2Sum computes the floating-point sum <math>s := a \oplus b</math> [[IEEE 754#Roundings to nearest|rounded to nearest]] and the floating-point error <math>t := a + b - (a \oplus b)</math> so that <math>s + t = a + b</math>, where <math>\oplus</math> and <math>\ominus</math> respectively denote the addition and subtraction rounded to nearest.
The error <math>t</math> is itself a floating-point number.

:'''Inputs''' floating-point numbers <math>a, b</math>
:'''Outputs''' rounded sum <math>s = a \oplus b</math> and exact error <math>t = a + b - (a \oplus b)</math>
:# <math>s := a \oplus b</math>
:# <math>a' := s \ominus b</math>
:# <math>b' := s \ominus a'</math>
:# <math>\delta_a := a \ominus a'</math>
:# <math>\delta_b := b \ominus b'</math>
:# <math>t := \delta_a \oplus \delta_b</math>
:# return <math>(s, t)</math>

Provided the floating-point arithmetic is correctly rounded to nearest (with ties resolved any way), as is the default in [[IEEE 754]], and provided the sum does not overflow and, if it underflows, [[gradual underflow|underflows gradually]], it can be proven that {{nowrap|<math>s + t = a + b</math>.}}<ref name="handbook"/><ref name="knuth-taocp-vol2">{{cite book
|last1=Knuth
|first1=Donald E.
|author-link=Donald Knuth
|title=The Art of Computer Programming, Volume II: Seminumerical Algorithms
|date=1998
|publisher=Addison–Wesley
|isbn=978-0-201-89684-8
|page=236
|edition=3rd
|url=https://www-cs-faculty.stanford.edu/~knuth/taocp.html
|access-date=2020-09-20
|archive-date=2017-07-16
|archive-url=https://web.archive.org/web/20170716132045/http://cs.stanford.edu/~uno/taocp.html
|url-status=live
}}</ref><ref name="moeller"/>

A variant of 2Sum called '''Fast2Sum''' uses only three floating-point operations, for floating-point arithmetic in radix 2 or radix 3, under the assumption that the exponent of <math>a</math> is at least as large as the exponent of <math>b</math>, such as when {{nowrap|<math>\left|a\right| \geq \left|b\right|</math>:}}<ref name="handbook"/><ref name="knuth-taocp-vol2"/><ref name="sterbenz">{{cite book
|last1=Sterbenz
|first1=Pat H.
|title=Floating-Point Computation
|date=1974
|publisher=Prentice-Hall
|location=Englewood Cliffs, NJ, United States
|isbn=0-13-322495-3
|pages=138–143
}}</ref><ref name="dekker">{{cite journal
|last1=Dekker
|first1=T.J.
|author-link=Theodorus Dekker
|title=A floating-point technique for extending the available precision
|journal=Numerische Mathematik
|date=June 1971
|volume=18
|issue=3
|pages=224–242
|doi=10.1007/BF01397083
|doi-access=free
|s2cid=63218464
|url=https://ir.cwi.nl/pub/9159
|access-date=2020-09-24
|archive-date=2020-07-19
|archive-url=https://web.archive.org/web/20200719135521/https://ir.cwi.nl/pub/9159/
|url-status=live
}}</ref>

:'''Inputs''' radix-2 or radix-3 floating-point numbers <math>a</math> and <math>b</math>, of which at least one is zero, or which respectively have normalized exponents <math>e_a \geq e_b</math>
:'''Outputs''' rounded sum <math>s = a \oplus b</math> and exact error <math>t = a + b - (a \oplus b)</math>
:# <math>s := a \oplus b</math>
:# <math>z = s \ominus a</math>
:# <math>t = b \ominus z</math>
:# return <math>(s, t)</math>

Even if the conditions are not satisfied, 2Sum and Fast2Sum often provide reasonable approximations to the error, i.e. <math>s + t \approx a + b</math>, which enables algorithms for compensated summation, dot-product, etc., to have low error even if the inputs are not sorted or the rounding mode is unusual.<ref name="handbook"/><ref name="moeller"/>
More complicated variants of 2Sum and Fast2Sum also exist for rounding modes other than round-to-nearest.<ref name="handbook"/>

== See also ==
*[[Kahan summation algorithm]]
*[[Round-off error]]
*[[Double-double arithmetic]]

== References ==
{{reflist}}

[[Category:Computer arithmetic]]
[[Category:Floating point]]
[[Category:Numerical analysis]]