Supplementary Notes
Interval Arithmetic in Fortran -- Some Specifics
presented by R. Baker Kearfott to meeting 136 of ANSI/X3J3 (Las Vegas,
Nevada, February 8, 1996)
page 3: "Overview -- Major Points:"
The phrase "thou shalt contain" was originally "thou shalt not
lie," truer to the original. If the result of an interval
operation or interval function evaluation contains the exact
range of the mathematical operation over all points in the
operands, then algorithms can be designed that don't lie.
That is, algorithms can be designed that always give
mathematically rigorous bounds on solutions, or that
rigorously prove that there are no solutions.
Concerning the phrase "thou shalt blend in:" Most of the
additions to the standard to include an interval data type
can be made as minor alterations to the wording of the
existing standard.
page 4: "Overview -- Some Features:"
The specification of interval intrinsics mandates that they
contain the range of the corresponding mathematical function
over the set of interval arguments. The holy grail for an
interval intrinsic is to return the closest floating point
interval to the actual mathematical result. However such a
requirement may make implementation too difficult or make
evaluation too inefficient in some instances. Thus, the
trade-off between "sharpness" and performance is left to the
implementer.
page 5: IEEE arithmetic helps with outward roundings. For example
(see page 6), in exact interval arithmetic,
[xl,xu] + [yl,yu] = [xl+yl,xu+yu]. IEEE defines the downward
rounding as the same result as computing the exact result, then
rounding into the nearest floating point number less than the
exact result, and the upward rounding as the same result as
computing the exact result, then rounding into the nearest
floating point number greater than the exact result. Thus,
if the result xl+xu were rounded down and xu+yu were rounded
up according to the IEEE specifications, an ideal interval
addition would result.
Two (case-insensitive) symbols, -INFINITY and INFINITY, should
also be defined. These correspond to negative infinity and
positive infinity in IEEE arithmetic, but should be defined
for all implementations. The symbol -INFINITY represents
something less than all floating point numbers, and INFINITY
represents something greater than all floating point numbers.
Intervals with one or both endpoints equal to these symbols
should be allowed, and arithmetic on them is defined,
consistently with IEEE arithmetic. The interval
() shall represent the empty set. In
general, intervals in which the upper end point is less than
the lower endpoint are non-standard. However, we envision
various useful non-standard extensions in this context.
page 6: Multiplication is sometimes implemented as a series of
eight cases, rather than four products followed by taking a
minimum and maximum. Implemented in software, which
implementation is most efficient is machine-dependent.
page 8: These specifications are those of "certainly true"
operators, true only if they are true for every selection of
real numbers in the range of the operands. Extensions can
include a set of "possibly true" operators, that are true
if there exists a selection of real numbers in the range
of the interval operands, and a set of "set-relational"
operators, true if the relation holds in a set-theoretic
sense.
page 9: The function ABS is an interval extension of the real function
ABS, consistent with the stipulation that interval extensions
contain the range. It is included in this table since it is
closely related to MAG and MIG. The same is true for the
function MAX.
page 11: In addition to the VE and VF formats, we will propose the
SE and SF formats, for single number output of intervals. The
basic representation of an interval as a single number is as
follows:
1. A single number without a decimal point represents an
interval whose lower and upper endpoints are identical
(a degenerate interval).
2. A single number with a decimal point represents
an interval whose endpoints are constructed by subtracting
and adding .5 units in the last decimal digit not exhibited.
Here are some examples of intervals represented by various
single numbers:
Single Number Interval represented
(<.1>) [0.05,.15]
(<1>) [1, 1]
(<.1000>) [.09995, .10005]
(<1E-1>) [0.1,0.1]
(<.0>) [-.05,.05]
(<0.E3>) [-0.5E3, 0.5E3]
This type of representation was implemented by G. W. Walster
in the "M77" compiler, that ran on CDC machines.
The SE and SF specifiers have the same form as the E and F
specifiers, i.e. SF. and SE.[E]. However, the
printed result will not always have digits past the
decimal point, since there may not be that many identical
significant digits of the left and right endpoints that are
equal. Similarly, for zero-width intervals, no digits past
the decimal point will be displayed. However, the number will
be justified as if all the digits specified by the format were
printed. If a number is too inaccrate to be represented
within a specified SF format, the entire field will be filled
with asterisks. Note that the "SF" format, when used for
zero-width intervals, is limited to integers. The
specifies the width of the numerical field, and not the spaces
taken by "(<" and ">)". Thus, the total width of an SE or SF
field would be +4.
Although the SE and SF specifiers can be used for both input
and output, they are most useful on output, since the VE and
VF specifiers will also accept single-number intervals on
input.
Interval "G" I/O and list-directed I/O is also defined,
consistently with corresponding real I/O and the above.
pages 13-14: The order of operations in interval expressions affects
the result of the expression, as indicated. However, certain
optimizations are clearly advantageous. For example, if each
variable in the expression occurs only once, then the result
in exact arithmetic (without outward roundings) is the exact
range. This is usually what is intended. Furthermore, there
is a correspondence between the amount of overestimation in an
interval expression and the accuracy of the expression if
evaluated with real data. The point is that there are things
that can be done at the compiler level to optimize the order
in which interval expressions are evaluated. The question
is: How could such reordering be done in a module?
=======================================================================
Questions for X3J3:
__________________
We are not totally satisfied with (), and we think that [A,B]
would be better. However "[" and "]" are not part of the Fortran
character set. Is there anything that can be done in this regard? I
have avoided "(" and ")" since it could cause confusion with complex
data, for certain types of I/O.