ISO/IEC JTC1/SC22/WG5 N1148
Requirement for the Development of Standardized Fortran Modules
for Interval Arithmetic including Full IEEE Arithmetic Support
(submitted by DIN WG for Fortran)
(A preliminary version of this requirement was submitted to X3J3 by
William Walster and Keith Bierman from SUN on August 29, 1995.)
The IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE 754-1985)
has been around for a decade. Today, a large majority of processors conforms
to this standard, and users have come to expect it on most platforms.
Unfortunately, even after a decade of IEEE hardware, software support of
the standard is still woefully incomplete and inadequate. This means that
certain operations and features which have been present in hardware for ten
years are still virtually inaccessible with current software and thus rarely
used. For example, no standardized programming language provides portable
and efficient access to the elementary operations with directed roundings,
and most languages still lack exception handling facilities. This is
particularly true of the Fortran language (even in its 1995 form), whose
future success as a programming language for scientific computing may
critically depend on the timely addition of such features.
IEEE conformance is supposed to be a property of a complete programming
system (see first 3 sentences of the IEEE standard), but at present it
is in fact only the property of certain hardware processors (if at all).
Up until now, no programming system achieves full compliance with the
IEEE standard at the programmer's level.
It is a widespread misconception that the use of a processor conforming
to (parts of) the IEEE standard will in itself greatly improve the quality
of computational results, where, in reality, performing all calculations
in the round-to-nearest mode generally affords only a very minor
accuracy advantage over other approximate calculations.
On the other hand, the judicious use of directed roundings to compute
guaranteed enclosures of solutions and solution sets enables numerical
results and mathematical statements of a new quality which are extremely
difficult or impossible to obtain by approximate computation.
In recent years, the field of Interval Analysis has attracted a lot of
international research interest. At the same time, the number of
application areas where safety and mathematical rigor are essential
has been growing steadily. All of these applications and algorithms
require full error/rounding control during the computational process
and document the urgent need for efficient interval arithmetic and
full IEEE arithmetic support in numerical programming languages.
In Fortran, this can best be achieved by a standardized specification of
the interfaces and semantics of a small set of Fortran modules providing a
convenient and fast implementation of interval arithmetic and direct and
efficient access to all operations and features of the IEEE standard.
***************************************************************************
The DIN working group for Fortran has conducted a German ballot on
whether this shall be a German requirement for the future development
of Fortran.
The vote was unanimously in favor: 11-0-0.
The following members of the DIN working group voted YES:
Ewald Bensch
Wilhelm Gehrke
Michael Hennecke
Friedrich Pluennecke
Walter Reichenbaecher
Karl-Heinz Rotthaeuser
Willi Schoenauer
Mok Kong Shen
Christian Tanasescu
Wolfgang Walter
Christian Weber
We feel compelled to reiterate the reasons why a normative specification
for an interval module is needed, and why it is not sufficient to simply
write an interval module employing only the means of Fortran.
The simple answer is that most problems persist unless there is a standard.
Typically, implementations are either not portable or extremely inefficient,
and, in many cases, both. Although there is almost global availability
of good hardware capabilities (IEEE 754 for example), all existing
standardized programming languages either do not allow access to these
capabilities, or they only provide very inefficient access (typically
slower by a factor of 5 to 100). Without a standard, most system suppliers
will not be motivated to provide good hardware and compiler support.
In Fortran, the following deficiencies with respect to IEEE 754 persist:
- no routines for setting the rounding mode,
- no direct access to arithmetic operations with directed roundings,
- no rounding control during conversion of constants and I/O data,
- no support for the special IEEE values (infinities, NaNs, ...),
- no access to the exception and trap flags of the processor,
- no exception handling.
The following goals can be achieved by standardizing a module or a
small set of modules (note that most of these goals will not be
achieved by writing a non-standardized module in a high-level language,
especially not simultaneously):
- data abstraction through the definition of a named data type and
the pertinent operations in a module or class,
- portability through the creation of a uniform, standardized interface
and a complete functional specification, which guarantees that the
syntax and the behavior/semantics are identical on all platforms,
- a choice of the implementation techniques, tools and resources
(programming languages, library routines, assembler code, ...),
- the possibility of a highly efficient, perhaps nearly optimal
implementation of all required operations and functions tailored to
the individual hardware platform, operating system, etc.,
- protection of vendor investment in the development of advanced,
modern systems,
- protection of user investment in program code that respects the
interfaces and specifications prescribed by the standard,
- full exploitation of the abilities and performance of the hardware,
- avoidance of the inefficiencies which are inevitable with a purely
high-level language implementation of the algorithms.
The importance of reliable arithmetic for real and complex numbers and
intervals in a programming language for scientific computing seems
obvious. This could become an important factor in choosing Fortran
over other languages.
Conclusion:
----------
DIN would therefore like to submit to ISO/IEC JTC1/SC22/WG5 the
requirement for the development of Standardized Fortran Modules
for Interval Arithmetic including Full IEEE Arithmetic Support.
*************************************************************************
History
-------
A lot of experience in implementing interval arithmetic in software,
firmware, and even hardware is available, some of it well over 20 years
old. Numerous libraries, modules, classes, and even language
extensions have been designed and implemented - with varying degress
of sophistication. Early implementations include an Algol 60 extension
called Triplex-Algol in Karlsruhe and an interval package from the
Mathematics Research Center in Madison using the Augment precompiler.
Some features were also provided by CDC FORTRAN compilers.
Other commercial products include IBM's High-Accuracy Arithmetic
Subroutine Library ACRITH and IBM's language extension (compiler)
ACRITH-XSC (High Accuracy Arithmetic - Extended Scientific Computation).
Other vendors (e.g. NAG) and computer algebra systems are starting to
provide interval arithmetic.
Recently, SUN and others have been getting very serious about providing
hardware and software support for interval arithmetic and for efficient
and complete IEEE arithmetic. The interest in this area has been
growing more rapidly in recent times, and the plan to finally speak
up matured in a group of engineers, scientists, and mathematicians who
need reliable numerical tools for much of their programming work
at their last meeting in September 95 in Wuppertal, Germany.
More than 100 scientists from 18 countries spoke about scientific
computing with numerical result verification, about interval methods
and algorithms, and about applications that depend on such tools.
On the last day, more than 50 attendees spontaneously signed a petition
asking WG5 to support the establishment of a standard for interval
analysis in Fortran. In October 95 in Kyoto, Japan, IFIP WG 2.5
(Numerical Software) unanimously supported a petition to the same effect.
In short: there is a community of Fortran users who are in desperate
need of fast, complete, convenient tools for reliable computing, i.e.
for computing guaranteed bounds on solutions and solution sets.
This community, which includes manufacturers, believes that one of
the best ways to achieve this goal - save introducing new intrinsic
types, operators, and procedures into the Fortran language itself -
is to develop a standardized set of modules for this purpose.
Baker Kearfott, a mathematician from the Univ. of South-Western
Louisiana who has a lot of experience in implementing and using
interval mathematics in a Fortran environment, has agreed to be
the PROJECT EDITOR, and a small working group will support him.
Wolfgang Walter has agreed to provide a SAMPLE IMPLEMENTATION in
Fortran 95, which, by its very nature, will have to be very
inefficient, leaving room for many vendor-specific and
hardware-dependent optimizations.
************************************************************************
The ideas and explanations below are intended to give a rough overview
of what is currently being discussed and tentatively planned. They are
imprecise and incomplete in many ways and by no means definitive.
Current Working Group Kernel:
----------------------------
Keith Bierman (SUN, WG5, X3J3)
George Corliss (Marquette Univ., Milwaukee)
Baker Kearfott (USL, Lafayette, Louisiana) - Project Editor
Bill Walster (SUN)
Wolfgang Walter (TU Dresden, WG5)
Many others have indicated their interest and support, e.g. more
than 50 scientists at the conference in Wuppertal.
Besides the discussions within the working group kernel, there has already
been a substantial amount of e-mail traffic on this subject - with a lot
of positive responses. Many people have already been reading about this
activity, including people on David Hough's news group, and there has
been a lot of supportive and open discussion on the issues involved.
General Plan:
------------
Development of a Standardized Set of Fortran Modules for Interval
Arithmetic including Full IEEE Arithmetic Support.
This development includes the following tasks:
Define a Fortran binding to IEEE primitives and features
Introduce the abstract data type INTERVAL
Require containment/enclosure of solutions (or solution sets)
Support elementary arithmetic operations
Support intrinsic functions of Fortran
Keep it rather simple and unrestrictive
Do not require high/optimal accuracy, except maybe as an option
Base document: Model implementations and preliminary documentation exist
(e.g. INTLIB by Baker Kearfott, FORTRAN-XSC by Wolfgang Walter)
Time scale: initial technical work: 1 year
reviewed and finalized ISO standard: 3 years
Some Practical Aspects:
----------------------
Interval arithmetic provides a way for users to have confidence in the
quality of their computations. It facilitates the solution of entire
classes of numerically difficult problems, and it can simplify the
algorithm choice.
Besides being good for error analysis, interval arithmetic is convenient
from a mathematical point of view: It can be the simplest, best way
to bound variations and ranges over intervals that are large in relation
to the roundoff threshold. This is important in many computations.
The two senses of interval relationals (possibly and certainly) force
implementors to come to grips with the intent of these tests. This
provides an incentive to implement more reliable algorithms. Without
interval arithmetic, random incorrect branches through code are more
likely. Carefully coded interval implementations can prevent this.
As more and more complex decisions are made on the basis of computer
simulation, the need to quantify the precision and accuracy of
computations increases, as well as the cost of being wrong.
Some Design Aspects:
--------------------
Hierarchy of modules
--------------------
There should probably be a small hierarchy of modules, e.g.
lev 0: A. a small module containing constants and parameters
and possibly fundamental data types for the whole package;
B. possibly a module providing some primitive error handling
(may change or disappear when true exception handling
becomes available);
lev 1: C. a module providing efficient and direct access to all
IEEE 754 operations and features including, in particular,
direct access to the 4 rouding modes, operations with directed
roundings, correct treatment of IEEE exceptional values such
as +0, -0, +oo, -oo, and NaNs, recognition of the 5 IEEE
exceptions, correctly rounded constant and I/O data conversion,
and other conversions between different data types/formats;
lev 2: D. a module providing all the necessary arithmetic and I/O
operations and functions for real intervals (all intrinsic
operations and all numerical intrinsic functions for which
an interval variant makes sense should be included);
------------------------------------------------------------------------
The next level could be omitted in the first proposal or specified as
an optional level:
lev 3: E. a module for complex interval arithmetic.
------------------------------------------------------------------------
Support for rounding modes
--------------------------
IEEE rounding modes can be supported either with a flag to control
the current rounding mode (nearest, down, up, zero) or with opcodes
(addn, addd, addu, addz). Either approach works. Which works better
is processor-dependent. If a processor has direct support for one,
it can handle the other, although at a higher cost. If we standardize
one interface, manufacturers of processors of the other type are penalized.
We thus recommend providing both. However, this will take some careful
wording to warn people that programming in one style only may cause
some inefficiencies. It seems impossible to attain optimal performance
on all platforms without some preprocessing/switching in the source code.
Support for IEEE special values
-------------------------------
The IEEE Standard 754 was designed quite explicitly to provide support
for interval arithmetic - even with unbounded intervals. This is the
main reason for having signed zeros and signed infinities. NaNs must
also be supported.
There is sufficient theoretical work on this to allow straightforward
implementation (see Popova in Interval Computations No. 4, 1994).
Interaction with other parts of Fortran development
---------------------------------------------------
There will clearly be a very intimate link to the TR on Exception
Handling since full IEEE conformance requires supporting the five
IEEE exceptions and traps.
To a somewhat lesser degree, interaction is required with the TR
dealing with parametrized data types. Simple parametrization
of a derived type by a single kind type parameter determining
the precision/representation of its component types would be
sufficient for our purposes.
Also, user-defined (derived-type) I/O will be required to make the
package complete. One may even think of making constants or
constructors "overloadable". From a more general viewpoint,
all of this could be subsumed under the heading "OOP".