C H A P T E R 1 |
Using the Interval Arithmetic Library |
Interval arithmetic is a system for computing with intervals of numbers. Because interval arithmetic always produces intervals that contain the set of all possible result values, interval algorithms have been developed to perform surprisingly difficult computations. For more information on interval applications, see the Interval Arithmetic Readme.
The goal of interval support in C++ is to stimulate development of commercial interval solver libraries and applications by providing program developers with:
Support and features are components of implementation quality. Not all possible quality of implementation features have been implemented. Throughout this book, various unimplemented quality of implementation opportunities are described. Additional suggestions from users are welcome.
As a consequence of evaluating any interval expression, a valid interval-supporting compiler must produce an interval that contains the set of all possible results. The set of all possible results is called the containment set (cset) of the given expression. The requirement to enclose an expression's cset is the containment constraint of interval arithmetic. The failure to satisfy the containment constraint is a containment failure. A silent containment failure (with no warning or documentation) is a fatal error in any interval computing system. By satisfying this single constraint, intervals provide otherwise unprecedented computing quality.
Given the containment constraint is satisfied, implementation quality is determined by the location of a point in the two-dimensional plane whose axes are runtime and interval width. On both axes, small is better. How to trade runtime for interval width depends on the application. Both runtime and interval width are obvious measures of interval-system quality. Because interval width and runtime are always available, measuring the accuracy of both interval algorithms and implementation systems is no more difficult than measuring their speed.
The Sun Forte Developer tools for performance profiling can be used to tune interval programs. However, in C++, no interval-specific tools exist to help isolate where an algorithm may gain unnecessary interval width. Quality of implementation opportunities include adding additional interval-specific code development and debugging tools.
All the normal language and compiler quality of implementation opportunities exist for intervals, including rapid execution and ease of use.
Valid interval implementation systems include a new additional quality of implementation opportunity: Minimize the width of computed intervals while always satisfying the containment constraint.
If an interval's width is as narrow as possible, it is said to be sharp. For a given floating-point precision, an interval result is sharp if its width is as narrow as possible.
The following statements apply to the width of intervals produced by the interval class:
By providing compiler optimization and hardware instruction support, interval operations are not necessarily slower than their floating-point counterparts. The following can be said about the speed of interval operators and mathematical functions:
The C++ interval class facilitates interval code development, testing, and execution.
Sun Forte Developer C++ includes the following interval extensions:
For examples and more information on these and other interval functions, see CODE EXAMPLE 2-8 through CODE EXAMPLE 2-10 and Section 2.9.4, Functions That Accept Interval Arguments.
Chapter 2 contains detailed descriptions of these and other interval features.
The compilation interface consists of the following:
It is a fatal error if at the end of command line processing -xia is set, and either -fsimple, -fns, or -ftrap is set to any value other than
To use the C++ interval arithmetic features, add the following header file to the code.
An example of compiling code using the -xia command-line option is shown here.
math% CC -o filename -xia filename.cc |
The C++ interval library supports the following common C++ compilation modes:
See the C++ Migration Guide and the C++ User's Guide for more information on these modes.
The following sections describe the ways that these compilation modes affect compilation of applications using the interval library.
In standard mode only, all interval types and symbols are defined within the namespace SUNW_interval. To write applications that compile in both standard mode and compatibility mode, use the following code.
#if __cplusplus >= 199711 using namespace SUNW_interval; #endif |
Some interval functions return boolean values. Because compatibility mode does not support boolean types by default, these functions are defined returning a type interval_bool, which is a typedef to an int (compatibility mode) or a bool (standard mode). Client code should use whatever type appropriate for boolean values and rely on the appropriate conversions from interval_bool to the client's boolean type. The library does not support explicit use of -features=bool or -features=no%bool.
The interval library requires the I/O mechanisms supplied in one of the three compilation modes listed in Section 1.2.5, The C++ Interval Class Compilation Interface. In particular, the flag -library=iostream must be specified on all compile and link commands if the application is using the standard mode with the traditional iostream library.
The examples in this section are designed to help new interval programmers to understand the basics and to quickly begin writing useful interval code. Modifying and experimenting with the examples is strongly recommended.
CODE EXAMPLE 1-1 is the interval equivalent of "hello world."
CODE EXAMPLE 1-1 uses standard output streams to print the labeled sum of the intervals [2, 3] and [4, 5].
The integer and floating-point numbers that can be represented in computers are referred to as internal machine representable numbers. These numbers are a subset of the entire set of extended (including - and +) real numbers. To make the distinction, machine representable numbers are referred to as internal and any number as external. Let x be an external (decimal) number or an interval endpoint that can be read or written in C++. Such a number can be used to represent either an external interval or an endpoint. There are three displayable forms of an external interval:
A positive or negative infinite interval endpoint is input/output as a case-insensitive string inf or infinity prefixed with a minus sign or an optional plus sign.
The empty interval is input/output as the case-insensitive string empty enclosed in square brackets, [...]. The string, "empty", can be preceded or followed by blank spaces.
See Section 2.4.1, Arithmetic Operators +, -, *, /, for more details.
Note - If an invalid interval such as [2,1] is converted to an internal interval, [-inf, inf] is stored internally. |
The interval declaration statement performs the same functions for interval data items as the double and int declarations do for their respective data items. CODE EXAMPLE 1-2 uses interval variables and initialization to perform the same operation as CODE EXAMPLE 1-1.
Variables X and Y are declared to be of type interval<double> variables and are initialized to [2, 3] and [2, 4], respectively. The standard output stream is used to print the labeled interval sum of X and Y.
Note - To facilitate code-example readability, all interval variables are shown as uppercase characters. Interval variables can be uppercase or lowercase in code. |
Full support for reading and writing intervals is provided. Because reading and interactively entering interval data can be tedious, a single-number interval format is introduced. The single-number convention is that any number not contained in brackets is interpreted as an interval whose lower and upper bounds are constructed by subtracting and adding 1 unit to the last displayed digit.
where [-1, +1]uld means that the interval [-1, +1] is added to the last digit of the preceding number. The subscript, uld, is a mnemonic for "unit in the last digit."
To represent a degenerate interval, a single number can be enclosed in square brackets. For example,
This convention is used both for input and constructing intervals out of an external character string representation. Thus, type [0.1] to indicate the input value is an exact decimal number, even though 0.1 is not machine representable.
During input to a program, [0.1,0.1] = [0.1] represents the point, 0.1, while using single-number input/output, 0.1 represents the interval
The input conversion process constructs a sharp interval that contains the input decimal value. If the value is machine representable, the internal machine approximation is degenerate. If the value is not machine representable, an interval having width of 1-ulp (unit-in-the-last-place of the mantissa) is constructed.
The simplest way to read and print interval data items is with standard stream input and output.
CODE EXAMPLE 1-3 is a simple tool to help users become familiar with interval arithmetic and single-number interval input/output using streams.
Note - The interval containment constraint requires that directed rounding be used during both input and output. With single-number input followed immediately by single-number output, a decimal digit of accuracy can appear to be lost. In fact, the width of the input interval is increased by at most 1-ulp, when the input value is not machine representable. See Section 1.3.5, Single-Number Input/Output and CODE EXAMPLE 1-6. |
One of the most frustrating aspects of reading interval output is comparing interval infima and suprema to count the number of digits that agree. For example, CODE EXAMPLE 1-4 and CODE EXAMPLE 1-5 shows the interval output of a program that generates different random-width interval data.
Note - Only program output is shown in CODE EXAMPLE 1-4 and CODE EXAMPLE 1-5. The code that generates the output is included with the examples located in the http://sun.com/forte/cplusplus/interval directory. |
Compare the output readability in CODE EXAMPLE 1-4 with CODE EXAMPLE 1-5.
In the single-number display format, trailing zeros are significant. See Section 2.8, Input and Output for more information.
Intervals can always be entered and displayed using the traditional [inf, sup] display format. In addition, a single number in square brackets denotes a point. For example, on input, [0.1] is interpreted as the number 1/10. To guarantee containment, directed rounding is used to construct an internal approximation that is known to contain the number 1/10.
CODE EXAMPLE 1-6 notes:
Note - The empty interval is supported in the interval class. The empty interval can be entered as [empty]. Infinite interval endpoints are also supported, as described in Section 1.3.2, interval External Representations. |
Writing arithmetic expressions that contain interval data items is simple and straightforward. Except for interval-specific functions and constructors, interval expressions look like floating-point arithmetic expressions, such as in CODE EXAMPLE 1-7.
A variety of interval-specific functions are provided. See Section 2.9.4, Functions That Accept Interval Arguments. Use CODE EXAMPLE 1-8 to explore how specific interval functions behave.
Use CODE EXAMPLE 1-9 to explore how some standard mathematical functions behave.
Information on interval code development tools is available online. See the Interval Arithmetic Readme for a list of interval web sites and other online resources.
To report a suspected interval error, send email to the following address:
Include the following text in the Subject line of the email message:
where mm/dd/yy is the month, day, and year of the message.
In Sun Forte Developer, interval data types are supported by dbx to the following extent:
For additional details on dbx functionality, see Debugging a Program With dbx.
Copyright © 2002, Sun Microsystems, Inc. All rights reserved.