2Sum

2Sum is a floating-point algorithm that computes the exact round-off error made when two floating-point numbers are added. Given two numbers a and b, it returns the rounded sum s and a second floating-point number t, the error, such that s plus t equals a plus b exactly. It does this with a short fixed sequence of floating-point additions and subtractions and needs no assumption about which of the two inputs is larger, provided the arithmetic is correctly rounded to nearest, as it is by default under IEEE 754, and the sum does not overflow. A cheaper variant called Fast2Sum uses only three operations but assumes the exponent of the first input is at least that of the second. The method was first published by Ole Moller in 1965, and the names 2Sum and Fast2Sum appear to have been applied later by Shewchuk in 1997. It is the building block behind compensated summation methods such as Kahan summation, dot-product routines and double-double arithmetic, which keep the lost low-order bits and so give results with low error.