Next: 4.8.1 Double precision floating Up: 4. Nonlinear Polynomial Solvers Previous: 4.7 Interval arithmetic Contents Index

4.8 Rounded interval arithmetic and its implementation

If floating point arithmetic is used to evaluate these interval arithmetic equations there is no guarantee that the roundings of the bounds are performed conservatively.^4.1 Rounded interval arithmetic (RIA) [254,255,4] ensures that the computed end points always contain the exact interval as follows:

$\displaystyle \;[a,b] + [c,d] = [(a+c)-\varepsilon_\ell, (b+d)+\varepsilon_u]\;,$
$\displaystyle \;[a,b] - [c,d] = [(a-d)-\varepsilon_\ell, (b-c)+\varepsilon_u]\;,$			(4.49)
$\displaystyle \;[a,b] \; \cdot \; [c,d] = [min(a\!\cdot\!c,a\!\cdot\!d,b\!\cdot... ..._\ell, max(a\!\cdot\!c, a\!\cdot\!d,b\!\cdot\!c,b\!\cdot\! d)+\varepsilon_u]\;,$
$\displaystyle \;[a,b] \: / \: [c,d] = [min(a/c, a/d, b/c, b/d)-\varepsilon_\ell, max(a/c, a/d, b/c, b/d)+\varepsilon_u]\;,$

where $\varepsilon_\ell$ and $\varepsilon_u$ are the units-in-last-place denoted by $ulp_\ell$ and for each separate floating point number resulting from the floating point operations giving the lower and upper bounds in (4.49). When performing standard operations for interval numbers using RIA, the lower bound is extended to include its previous consecutive FP number, which is smaller than the lower bound by $ulp_\ell$ . Similarly, the upper bound is extended by to include its next consecutive FP number. Thus, the width of the result is enlarged by $ulp_\ell+ulp_u$ and the resulting enlarged interval contains the exact interval. The RIA concept has been applied to topologically reliable approximation of curves and surfaces [57,58], robust visualization [427], and approximation of uncertain measured data [425].

Before describing the details of the PP algorithm in RIA, let us briefly summarize the IEEE standard binary representation for double precision floating point numbers [4].

Footnotes

... conservatively.^4.1: This statement is true only for the default IEEE-754 rounding mode of round towards nearest [10]. The subject of hardware rounding modes will be discussed thoroughly later.

Subsections

Next: 4.8.1 Double precision floating Up: 4. Nonlinear Polynomial Solvers Previous: 4.7 Interval arithmetic Contents Index

December 2009