From wwalter@math.tu-dresden.de Fri Nov 3 00:49:42 1995 Received: from RMAIL.urz.tu-dresden.de (RMAIL.urz.tu-dresden.de [141.30.66.2]) by dkuug.dk (8.6.12/8.6.12) with SMTP id AAA14640 for ; Fri, 3 Nov 1995 00:49:36 +0100 Received: from NBTF01.math.tu-dresden.de by RMAIL.urz.tu-dresden.de with SMTP (PP) id <03913-0@RMAIL.urz.tu-dresden.de>; Fri, 3 Nov 1995 00:44:01 +0100 Received: from NWRW09.math.tu-dresden.de by NBTF01.math.tu-dresden.de (AIX 3.2/UCB 5.64/4.03) id AA12598; Fri, 3 Nov 1995 00:49:23 +0100 From: wwalter@math.tu-dresden.de (Wolfgang Walter) Received: by NWRW09.math.tu-dresden.de (5.0/SMI-SVR4) id AA03398; Fri, 3 Nov 1995 00:49:23 --100 Message-Id: <9511022349.AA03398@NWRW09.math.tu-dresden.de> Subject: German Requirement for Interval Arithmetic To: SC22WG5@dkuug.dk (ISO/WG5 for Fortran) Date: Fri, 3 Nov 1995 00:49:23 +0100 (MET) X-Mailer: ELM [version 2.4 PL23] Content-Type: text Content-Length: 16191 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. Split existing Fortran Work Item for this development: 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".