T. Hickey
Q. Ju
Abstract
We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for computing these operations assuming exact real arithmetic. Next, we define interval arithmetic operations on intervals with IEEE 754 floating point endpoints to be sound and optimal approximations of the real interval operations and we show that the IEEE standard's specification of operations involving the signed infinities, signed zeros, and the exact/inexact flag are such as to make a correct and optimal implementation more efficient. From the resulting theorems, we derive data that are sufficiently detailed to convert directly to a program for efficiently implementing the interval operations. Finally, we extend these results to the case of general intervals, which are defined as connected sets of reals that are not necessarily closed.
- ALEFELD, G., AND HERZBERGER, J. 1983. Introduction to Interval Computations. Academic Press, Orlando, Fla.]]Google Scholar
- BENHAMOU,F.,AND OLDER, W. J. 1997. Applying interval arithmetic to real, integer, and Boolean constraints. J. Logic Prog. 32, 1-24.]]Google Scholar
- FORSYTHE, G. E. 1970. Pitfalls of computation, or why a math book isn't enough. Amer. Math. Monthly 77, 931-956.]]Google Scholar
- HAMMER, R., HOCKS, M., KULISCH, U., AND RATZ, D. 1993. Numerical Toolbox for Verified Computing I. Springer-Verlag, New York.]]Google Scholar
- HANSEN, E. 1992. Global Optimization Using Interval Analysis. Marcel Dekker.]]Google Scholar
- HANSON, R. J. 1968. Interval arithmetic as a closed arithmetic system on a computer. Tech. Rep. 197. Jet Propulsion Laboratory.]]Google Scholar
- HICKEY, T. J. 2000a. CLIP: A CLP(Intervals) Dialect for Metalevel Constraint Solving. In Proceedings of PADL'00. Lecture Notes in Computer Science, vol. 1753. Springer-Verlag, New York.]] Google Scholar
- HICKEY, T. J. 2000b. Analytic constraint solving and interval arithmetic. In Proceedings of the 27th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (Jan.). ACM, New York.]] Google Scholar
- HICKEY, T. J., QIU, Z., AND VAN EMDEN, M. H. 2000. Interval constraint plotting for interactive visual exploration of implicitly defined relations. Special issue on Reliable Geometric Computations. Rel. Comput. 6,1.]]Google Scholar
- KAHAN, W. M. 1968. A more complete interval arithmetic. Tech. rep. Univ. Toronto, Toronto, Ont., Canada.]]Google Scholar
- LIPSCHUTZ, S. 1965. General Topology. Schaum's Outline Series.]]Google Scholar
- MOORE, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J.]]Google Scholar
- NOVOA M. 1993. Theory of preconditioners for the interval Gauss-Seidel method and exis-tence/ uniqueness theory with interval Newton methods. Dept. Mathematics, Univ. Southwestern Louisiana.]]Google Scholar
- OLDER, W. J. 1989. Interval arithmetic specification. Tech. rep. Bell-Northern Research Computing Research Laboratory.]]Google Scholar
- RALL, L. B. 1969. Computational solution of nonlinear operator equations. Wiley, New York.]]Google Scholar
- RATZ, D. 1996. On extended interval arithmetic and inclusion isotonicity. Institut fur Angewandte Mathematik, Universit~t Karlsruhe.]]Google Scholar
- STOLFI, J., AND DE FIGUEIREDO, L. 1997. Self-Validated Numerical Methods and Applications. IMPA, Rio de Janiero, Brazil.]]Google Scholar
- VAN HENTENRYCK, P., MICHEL, L., AND DEVILLE, Y. 1997. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, Mass.]]Google Scholar
- WALSTER, G. W. 1996. The extended real interval system. Available on the internet, http://www.mscs.mu.edu / globsol / readings.html.]]Google Scholar
- WALSTER,G.W.,AND HANSEN, E. R. 1998. Interval Algebra, Composite Functions and Dependence in Compilers. Available on the internet, http://www.mscs.mu.edu /globsol /readings.html.]]Google Scholar
Index Terms
- Interval arithmetic: From principles to implementation
Recommendations
Mathematics and Speed for Interval Arithmetic: A Complement to IEEE 1788
After a short introduction, the article begins with an axiomatic definition of rounded arithmetic. The concepts of rounding and of rounded arithmetic operations are defined in an axiomatic manner fully independent of special data formats and encodings. ...
Complex interval arithmetic
Complex interval arithmetic is defined using real interval arithmetic. Complex interval division is defined so as to assure smallest possible resulting intervals.
Comments