Sterbenz lemma

In floating-point arithmetic, the Sterbenz lemma or Sterbenz' lemma[1] is a theorem giving conditions under which floating-point differences are computed exactly. It is named after Pat H. Sterbenz, who published it as Theorem 4.3.1 in his 1974 book Floating-Point Computation.[2]

The Sterbenz lemma states that for a floating-point number system with subnormal numbers, such as IEEE 754 binary64, if ${\displaystyle x}$ and ${\displaystyle y}$ are floating-point numbers such that

$${\displaystyle {\frac {y}{2}}\leq x\leq 2y}$$

then ${\displaystyle x-y}$ is also a floating-point number. Thus, the floating-point subtraction ${\displaystyle x\ominus y=\operatorname {fl} (x-y)=x-y}$ is computed exactly.

Relation to catastrophic cancellation

The Sterbenz lemma may be contrasted with the phenomenon of catastrophic cancellation:

• The Sterbenz lemma asserts that if ${\displaystyle x}$ and ${\displaystyle y}$ are sufficiently close floating-point numbers then their difference ${\displaystyle x-y}$ is computed exactly by floating-point arithmetic ${\displaystyle x\ominus y=\operatorname {fl} (x-y)}$, with no rounding needed.
• The phenomenon of catastrophic cancellation is that if ${\displaystyle {\tilde {x}}}$ and ${\displaystyle {\tilde {y}}}$ are approximations to true numbers ${\displaystyle x}$ and ${\displaystyle y}$—whether the approximations arise from prior rounding error or from series truncation or from physical uncertainty or anything else—the error of the difference ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ from the desired difference ${\displaystyle x-y}$ is inversely proportional to ${\displaystyle x-y}$. Thus, the closer ${\displaystyle x}$ and ${\displaystyle y}$ are, the worse ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ may be as an approximation to ${\displaystyle x-y}$, even if the subtraction itself is computed exactly.

In other words, the Sterbenz lemma shows that subtracting nearby floating-point numbers is exact, but if the numbers you have are approximations then even their exact difference may be far off from the difference of numbers you wanted to subtract.

Use in numerical analysis

The Sterbenz lemma is instrumental in proving theorems on error bounds in numerical analysis of floating-point algorithms. For example, Heron's formula

$${\displaystyle A={\sqrt {s(s-a)(s-b)(s-c)}}}$$

for the area of triangle with side lengths ${\displaystyle a}$, ${\displaystyle b}$, and ${\displaystyle c}$, where ${\displaystyle s=(a+b+c)/2}$ is the semi-perimeter, may give poor accuracy for long narrow triangles if evaluated directly in floating-point arithmetic. However, the alternative formula

$${\displaystyle A={\frac {1}{4}}{\sqrt {{\bigl (}a+(b+c){\bigr )}{\bigl (}c-(a-b){\bigr )}{\bigl (}c+(a-b){\bigr )}{\bigl (}a+(b-c){\bigr )}}}}$$

can be proven, with the help of the Sterbenz lemma, to have low forward error for all inputs.[3][4][5]

References

1. Muller, Jean-Michel; Brunie, Nicolas; de Dinechin, Florent; Jeannerod, Claude-Pierre; Joldes, Mioara; Lefèvre, Vincent; Melquiond, Guillaume; Revol, Nathalie; Torres, Serge (2018). Handbook of Floating-Point Arithmetic (2nd ed.). Gewerbestrasse 11, 6330 Cham, Switzerland: Birkhäuser. p. 101. doi:10.1007/978-3-319-76526-6. ISBN 978-3-319-76525-9.CS1 maint: location (link)
2. Sterbenz, Pat H. (1974). Floating-Point Computation. Englewood Cliffs, NJ, United States: Prentice-Hall. p. 138. ISBN 0-13-322495-3.
3. Kahan, W. (2014-09-04). "Miscalculating Area and Angles of a Needle-like Triangle" (PDF). Lecture Notes for Introductory Numerical Analysis Classes. Retrieved 2020-09-17.
4. Goldberg, David (March 1991). "What every computer scientist should know about floating-point arithmetic". ACM Computing Surveys. New York, NY, United States: Association for Computing Machinery. 23 (1): 5–48. doi:10.1145/103162.103163. ISSN 0360-0300. Retrieved 2020-09-17.
5. Boldo, Sylvie (April 2013). Nannarelli, Alberto; Seidel, Peter-Michael; Tang, Ping Tak Peter (eds.). How to Compute the Area of a Triangle: a Formal Revisit. 21st IEEE Symposium on Computer Arithmetic. Computer Arithmetic, 2009. Arith 2009. 19Th IEEE Symposium on. IEEE Computer Society. pp. 91–98. doi:10.1109/ARITH.2013.29. ISBN 978-0-7695-4957-6. ISSN 1063-6889.