In floating-point arithmetic, the Sterbenz lemma or Sterbenz's lemma[1] is a theorem giving conditions under which floating-point differences are computed exactly. It is named after Pat H. Sterbenz, who published a variant of it in 1974.[2]

Sterbenz lemma — In a floating-point number system with subnormal numbers, if and are floating-point numbers such that

then is also a floating-point number. Thus, a correctly rounded floating-point subtraction

is computed exactly.

The Sterbenz lemma applies to IEEE 754, the most widely used floating-point number system in computers.

Proof

edit

Let   be the radix of the floating-point system and   the precision.

Consider several easy cases first:

  • If   is zero then  , and if   is zero then  , so the result is trivial because floating-point negation is always exact.
  • If   the result is zero and thus exact.
  • If   then we must also have   so  . In this case,  , so the result follows from the theorem restricted to  .
  • If  , we can write   with  , so the result follows from the theorem restricted to  .

For the rest of the proof, assume   without loss of generality.

Write   in terms of their positive integral significands   and minimal exponents  :

 

Note that   and   may be subnormal—we do not assume  .

The subtraction gives:

 

Let  . Since   we have:

  •  , so  , from which we can conclude   is an integer and therefore so is  ; and
  •  , so  .

Further, since  , we have  , so that

 

which implies that

 

Hence

 

so   is a floating-point number. ◻

Note: Even if   and   are normal, i.e.,  , we cannot prove that   and therefore cannot prove that   is also normal. For example, the difference of the two smallest positive normal floating-point numbers   and   is   which is necessarily subnormal. In floating-point number systems without subnormal numbers, such as CPUs in nonstandard flush-to-zero mode instead of the standard gradual underflow, the Sterbenz lemma does not apply.

Relation to catastrophic cancellation

edit

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

  • The Sterbenz lemma asserts that if   and   are sufficiently close floating-point numbers then their difference   is computed exactly by floating-point arithmetic  , with no rounding needed.
  • The phenomenon of catastrophic cancellation is that if   and   are approximations to true numbers   and  —whether the approximations arise from prior rounding error or from series truncation or from physical uncertainty or anything else—the error of the difference   from the desired difference   is inversely proportional to  . Thus, the closer   and   are, the worse   may be as an approximation to  , 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 one has are approximations then even their exact difference may be far off from the difference of numbers one wanted to subtract.

Use in numerical analysis

edit

The Sterbenz lemma is instrumental in proving theorems on error bounds in numerical analysis of floating-point algorithms. For example, Heron's formula   for the area of triangle with side lengths  ,  , and  , where   is the semi-perimeter, may give poor accuracy for long narrow triangles if evaluated directly in floating-point arithmetic. However, for  , the alternative formula   can be proven, with the help of the Sterbenz lemma, to have low forward error for all inputs.[3][4][5]

References

edit
  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. Lemma 4.1, p. 101. doi:10.1007/978-3-319-76526-6. ISBN 978-3-319-76525-9.{{cite book}}: CS1 maint: location (link)
  2. ^ Sterbenz, Pat H. (1974). Floating-Point Computation. Englewood Cliffs, NJ, United States: Prentice-Hall. Theorem 4.3.1 and Corollary, 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. 23 (1). New York, NY, United States: Association for Computing Machinery: 5–48. doi:10.1145/103162.103163. ISSN 0360-0300. S2CID 222008826. 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. IEEE Computer Society. pp. 91–98. doi:10.1109/ARITH.2013.29. ISBN 978-0-7695-4957-6. ISSN 1063-6889.