[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

Interval FAQ
Jens Maurer - C++ class library for intervals

From Jens Maurer (jmaurer@menuett.rhein-main.de)

I've had a look at the two C++ interval arithmetic packages available via www.cs.utep.edu/interval-comp/main.html, namely RVInterval 1.1.1 (www-math.cudenver.edu/~rvan/Software.html) and PROFIL/BIAS (www.ti3.tu-harburg.de/Software/PROFIL.html). From a software design perspective, I felt that both were inadequate. Most importantly, they are not templated, so they always employ "double" as the underlying type.

Thus, I have written another C++ package with the following features:

  1. Configurable base type (float, double, long double, or even your own floating-point like type; I've included an example using a rational type).
  2. Configurable behavior for out-of-range arguments (exception or NaN)
  3. Abstracted rounding-mode control into a separate class to allow easy adaption to the computing environment.
  4. Transcendental functions implemented.
It is available at www.rhein-main.de/people/jmaurer/interval.tar.gz for testing now, but its final place will be at www.boost.org

You may want to adapt the Makefile to suit your C++ compiler and its options. I've tested the package on gcc 2.95.2, and I hope I've removed all things which prevented Microsoft Visual C++ 6.0 SP3 from compiling it as well.

If you have any suggestions for improvement, please send them in. In particular, I feel that the name of the current "dist" function is unintuitive.

Originally, I only intended the package to assess rounding errors in lengthy computations. Since then, I've learned that there are other application domains where interval arithmetic is useful, so I've provided some utility functions for set-like operations, affine transforms etc. as well.

What is the current preference among the numeric computing community regarding behavior on out-of-range argument values? I've read W. Kahan's "Lecture Notes on the Status of IEEE Standard 754 for Binary Floating Point Arithmetic" which seems to imply that raising exceptions has growing support. C++ provides language-based exceptions, but they are not required to be raised for illegal floating-point operations.

Thank you for your help.
Jens Maurer

See also Interval compilers and programming environments

Response by Jeremy Siek:

(jsiek@engr.sgi.com), Univ. of Notre Dame and SGI C++ Library & Compiler Group:

The over-arching advantage of this new interval class is that it would be suitable for acceptance into the C++ standard. The core interface follows the design principles used for the C++ std::complex class. This uniform standard interface is particularly important for modern C++ libraries that use generic programming, and allows intervals to be used seemlessly in place of other numeric types. In terms of the functionality and implementation, the class is quite similar to the existing interval arithematic software that I have seen. The design goal of this interval class was to take the best features of the existing software, and package it in an interface that follows C++ stardard guidelines.

The group of C++ experts at www.boost.org (many of whom are on the C++ stardard committee) has reviewed this interval class to ensure that the interface would be appropriate for standardization. It would be excellent if the reliable computing community also reviewed this class, to ensure that the functionality meets your needs, and that the implementation provides that functionality in a high-quality manner.

Jeremy Siek

Response by George Corliss:

(georgec@mscs.mu.edu), Marquette University.

Jens Maurer: What is the current preference among the numeric computing community regarding behavior on out-of-range argument values?

I would say the interval community is not of a single mind on this. For the view that there are NO exceptional conditions, see www.mscs.mu.edu/~globsol/walster-papers.html, especially

The Extended Real Interval System,
G. William (Bill) Walster,
extended_intervals.ps (Postscript - 295 Kb) 29 April 1998
Figure 1, page 8 (Postscript - 130 Kb)
Figures, pages 38 - 42. (Postscript - 188 Kb)
Abstract: Three extended real interval systems are defined and distinguished by their implementation complexity and result sharpness. The three systems are closed with respect to interval arithmetic and the enclosure of functions and relations, notwithstanding domain restrictions or the presence of singularities.
Interval Extensions of Real Functions with Finite Domains,
G. William (Bill) Walster,
domain.ps (Postscript - 84 Kb) 28 April 1998.
Abstract: Alternatives are considered for constructing interval enclosures of real functions with finite domains.

See also Interval compilers and programming environments

Response by J. Wolff v Gudenberg:

(wolff@informatik.uni-wuerzburg.de), University of Wuerzburg

We have prepared a very similar C++ library for interval arithmetic. It will be published in about 4-6 weeks. It implements all the extensions described in B. Walster's papers cited by Corliss.

For more information see www.imada.sdu.dk/~kornerup/RNC4/papers/p03.ps

J Wolff v Gudenberg

More from Response by Jens Maurer:

(jmaurer@menuett.rhein-main.de)

Thank you very much for the helpful comments and documentation pointers.

Thanks to your comments and after reading some of the papers, I know that my implementation is lacking. However, I feel that the important issue is the interface; after the interface is agreed upon, the implementation can be repaired easily.

With a common interface where all C++ interval packages agree, the implementation becomes interchangeable. This allows for

I understand that Dmitri Chiriaev and William Walster did exactly that for a FORTRAN extension.

There are several interval packages in existence, which all have different interfaces. This not only concerns function names, but also semantics. Let me highlight a few differences which hamper re-use of application software with different interval packages:

I understand that the decision in some of these items depends on the application domain, and thus the item should be a configuration option for the interval class. It seems important to me to identify the resulting space of configuration options.

Jens Maurer.

Response by R. Baker Kearfott:

(rbk@louisiana.edu), University of Louisiana at Lafayette

Jens Maurer:

>I understand that Dmitri Chiriaev and William Walster did exactly
>that for a FORTRAN extension.
We almost convinced the Fortran committee of requiring an intrinsic interval type in the standard. As a member of those committees (US X3J3 and international WG5), I organized input to the committee for two years. For about half of this time, an interval data type was a stated requirement for Fortran 2000. In the end, some disagreements within the interval community coupled with resistance on the part of some vendors to a technology they perceived as different, untested and with uncertain demand, killed the requirement. I have archives from a mailing list for discussion of the proposed standard. There are also other documents associated with the standardization effort.

The Chiriaev / Walster (and others) implementation within Sun's Fortran compiler benefits from the standardization effort, but goes beyond it in several ways. Most importantly, Walster et al have put effort into considering intervals resulting from operations such as [1,2] / [-1,1] or SQRT([-1,1]) to develop an exception-free system (using infinities for end points).

Precursors to the standardization effort are Walster's early library INTLIB, a library for an intrinsic Fortran data type for the Minnesota M77 compiler for CYBER 175 machines, and my Fortran 90 module INTERVAL_ARITHMETIC (ACM TOMS Algorithm 763). (My module uses the FORTRAN 77 module INTLIB, although it is unrelated to Walster's work; I was unaware that Bill had named his library INTLIB when I developed my INTLIB.)

Wolfgang Walter II has also been a player in the standardization process for intervals, especially as head of the German delegation to the international committee. He also developed a module that partially implements the proposed standard of the time.

I am hoping that we will all examine Sun's Fortran compiler. We may or may not agree with precise details, but, in any case, it represents a milestone from which we can start, if we perceive we need to go further. We should send our comments, suggestions, and criticism either here or to a support mailing list at

sun-interval-fortran-questions@interval.louisiana.edu

Bill Walster (Bill.Walster@eng.sun.com), Sun Microsystems, adds:
For sure, our soon to be released compiler has benefitted from the helpful work, comments and suggestions of many people, including Baker and those he listed, above. We hope the above mailing list will be actively used as a forum for getting questions answered and to express positive and negative comments.

Jens Maurer:

> - We could specify that the FPU rounding mode is undefined after
>some interval arithmetic operation, or that it will not be altered,
>i.e. rounding mode changes are always local to an operation.  The
>latter specification is useful if you mix interval and point
>arithmetic, for example.  From a software design perspective, I think
>it is inacceptable to have an indeterminate rounding mode after
>some interval arithmetic operation, rendering all future built-in
>point operations invalid.
Yes, specifying "undefined" allows some wiggle-room. In particular, different computer architectures switch rounding modes in different ways. Interval arithmetic can be efficiently implemented with just a single rounding mode (either "round-down" or "round-up"); that, I think, is an efficient option for most architectures. Otherwise, the best architecture for doing a sequence of unrelated computations interspersed with floating-point computations appears to be associating the rounding mode with the operation itself, rather than with a flag that is switched in the FPU.

If the architecture is unknown, specifying that the rounding mode is "undefined" after an operation lets the interval operations be efficient, but may cause inefficiencies later due to having to change the rounding mode back to a desired value.

Bill Walster (Bill.Walster@eng.sun.com), Sun Microsystems, adds:
In our f95 implementation, we guarantee that intervals do not produce any side effects on non-interval code. In particular, we "logically" restore the rounding mode after every interval operation.

Jens Maurer:

> - Behaviour on illegal operations such as sqrt(-1): Throw an exception,
>or do your best and continue (see the specification by Dmitri Chiriaev
>and William Walster).  From a C++ software design perspective, I think
>it is inacceptable to just terminate the program, but on the other
>hand, continuing might be inappropriate as well.  That's where C++
>exceptions come in handy.
The above has been the subject of some controversy. My perception is that, in some contexts, you will want to throw an exception, and, in others, you will want to continue.

Fortran does not have user-defined exceptions. The reasons, as I understand them, include efficiency. Fortran is a very good array-processing language, and there are major questions about what to do if an exception occurs in a component while an array operation is executing on an advanced-architecture machine.

Bill Walster (Bill.Walster@eng.sun.com), Sun Microsystems, adds:
The system we have implemented in f95 is set-based. The result of an operation or function evaluated at a point that is outside the closure of its domain is the empty set, or empty interval. Depending on the context, an empty result of an arithmetic operation or function evaluation may or may not indicate that an error has been made.

An exception-like feature is needed to provide a test for expression continuity, which is an assumption for the interval Newton algorithm and the Brouwer fixed-point theorem. This will only be needed in special circumstances and therefore needs to be invokable only when required.

Jens Maurer:

> - Behaviour of overloaded operator< : There is the choice of
>certainly-less-than, possibly-less-than and subset-of.
My reading is that the most commonly used meaning is "certainly less than", although others may disagree :-) In my view, the important thing is that non-interval-experts using interval arithmetic understand the distinction.
Bill Walster (Bill.Walster@eng.sun.com), Sun Microsystems, adds:
The most important practical application for this syntactic sugar I have uncovered is to make it easy to construct "complete" sets of relational statements. This is important to avoid hiding an empty result that could be the indication of an error condition. Otherwise, depending on the application, one or the other sense of relational operator may be what makes the most sense in the particular context.

Jens Maurer:

> - From a software design perspective, the use of macros (instead of
>template parameters) is not desirable.  I shall check out the
>performance disadvantage for templates claimed by Juergen Wolff
>von Gudenberg in the paper advertised in his mail.  Frankly, I have
>a hard time believing it.
Can we race J{\"u}rgen's package and yours under similar conditions?

By the way, in developing template-like features in Fortran 200x, a consideration of the standardization committee was "avoiding performance hits as you see in C++".

R. Baker Kearfott


[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

If you have a question related to validated computing, interval analysis, or related matters, I recommend

This page URL: http://www.mscs.mu.edu/~georgec/IFAQ/maurer1.html
Last modified March 22, 19100. Send comments to (georgec@mscs.mu.edu)
Access count since 20 Apr 1999 : Graphical counter