From ae38@iamk4524.mathematik.uni-karlsruhe.de Wed Jan 5 17:20:06 1994 Received: from iamk4524.mathematik.uni-karlsruhe.de by dkuug.dk with SMTP id AA16599 (5.65c8/IDA-1.4.4j for ); Wed, 5 Jan 1994 16:18:47 +0100 Received: from localhost (ae38@localhost) by iamk4524.mathematik.uni-karlsruhe.de (8.6.4/8.6.4) id QAA25099 for SC22WG5@dkuug.dk; Wed, 5 Jan 1994 16:20:07 +0100 From: Wolfgang Walter Message-Id: <199401051520.QAA25099@iamk4524.mathematik.uni-karlsruhe.de> Subject: Some Comments on a Note by Mary Payne To: SC22WG5@dkuug.dk (Fortran 90) Date: Wed, 5 Jan 1994 16:20:06 +0100 (MET) X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 17645 X-Charset: ASCII X-Char-Esc: 29 %%% SOME COMMENTS ON A NOTE BY MARY PAYNE %%% ------------------------------------- %%% %%% by Ulrich Kulisch and Wolfgang V. Walter %%% This is a LaTeX document. It needs to be translated using %%% the standard LaTeX (lplain) format, producing a *.dvi file %%% which can then be viewed or printed. %%% For those of you who do not have access to LaTeX, I am also %%% sending a POSTSCRIPT VERSION by separate e-mail. \documentstyle[12pt,twoside,fleqn]{article} \sloppy \flushbottom \setlength{\topmargin}{0in} \setlength{\oddsidemargin}{0.0in} \setlength{\evensidemargin}{0.0in} \setlength{\textwidth}{6.50in} \setlength{\textheight}{9.00in} \setlength{\parindent}{0em} \setlength{\parskip}{5pt plus 2pt minus 1pt} \newenvironment{myequationnew}[4]{ \begin{tabular*}{\textwidth}{@{}llrr@{}} %%% \hspace*{\leftmargini} \makebox[20mm][l]{ #1 } & \makebox[50mm][l]{$ #2 $} & \makebox[40mm][l]{ #3 } & \hfill \makebox[40mm][r]{\sl #4} \\ }{\end{tabular*} } \newcommand{\Round} {\mbox{$\bigcirc$}} \newcommand{\Near} {\raisebox{-0.4ex}{\large $\Box$}} \newcommand{\Zero} {\raisebox{-0.2ex}{\large $\sqcup$}} \newcommand{\Away} {\raisebox{-0.2ex}{\large $\sqcap$}} \newcommand{\Up} {\raisebox{-0.2ex}{$\bigtriangleup$}} \newcommand{\Down} {\raisebox{+0.2ex}{$\bigtriangledown$}} \newcommand{\Ival} {\raisebox{-0.2ex}{\large $\Diamond$}} \newcommand{\circirc} {\mbox{$\:\circ\;\!\!\!\!\!\!\Round$}} \newcommand{\ariops} {$+, -, \,*\,,\,/\,$} \newcommand{\quadr} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){}} \end{picture}} \newcommand{\qplus} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ + $}} \end{picture}} \newcommand{\qminus} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ - $}} \end{picture}} \newcommand{\qmul} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ * $}} \end{picture}} \newcommand{\qdiv} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ / $}} \end{picture}} \newcommand{\qint} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ \int $}} \end{picture}} \newcommand{\qcirc} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\scriptsize $ \circ $}} \end{picture}} \newcommand{\qdot} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) %%% \put(2,0){\framebox(6,6){\scriptsize $ \:\!\! \cdot $}} \put(2,0){\framebox(6,6){$\cdot$}} \end{picture}} \newcommand{\qplusminus} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(2,0){\framebox(6,6){\tiny $ \pm $}} \end{picture}} \newcommand{\raute}{\diamondsuit} \newcommand{\rplus} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(2.5,1.5){\scriptsize $ + $} \end{picture}} \newcommand{\rminus} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(2.5,1.5){\scriptsize $ - $} \end{picture}} \newcommand{\rmul} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(3.5,1.5){\scriptsize $ * $} \end{picture}} \newcommand{\rdiv} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(3.5,1.5){\scriptsize $ / $} \end{picture}} \newcommand{\rcirc} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(3.5,1.5){\scriptsize $ \circ $} \end{picture}} \newcommand{\rint} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(2,0.1){$ \int $} \end{picture}} \newcommand{\rdot} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(1,0){$\diamondsuit$} \put(2.5,1.5){\scriptsize $\:\cdot$} % \; ??? \end{picture}} \newcommand{\braute}[1] {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(5,6){\makebox(0,0){\Huge$\diamondsuit$}} \put(5,6){\makebox(0,0){\scriptsize #1}} \end{picture}} \newcommand{\plusdown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} \put(4.5,1.5){\scriptsize $ \:\!\! + $} \end{picture}} \newcommand{\plusup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} \put(4.5,1.5){\scriptsize $ \:\!\! + $} \end{picture}} \newcommand{\minusdown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} \put(4.5,1.5){\scriptsize $ \:\!\! - $} \end{picture}} \newcommand{\minusup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} \put(4.5,1.5){\scriptsize $ \:\!\! - $} \end{picture}} \newcommand{\muldown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} \put(4.5,1.5){\scriptsize $ * $} \end{picture}} \newcommand{\mulup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} \put(4.5,1.5){\scriptsize $ * $} \end{picture}} \newcommand{\divdown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} \put(4.5,1.5){\scriptsize $ / $} \end{picture}} \newcommand{\divup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} \put(4.5,1.5){\scriptsize $ / $} \end{picture}} \newcommand{\dotdown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} %%% \put(4.5,1.5){\scriptsize $\,\cdot$} \put(4.5,0){$\hspace{0.5pt} \cdot$} \end{picture}} \newcommand{\dotup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} %%% \put(4.5,1.5){\scriptsize $\,\cdot$} \put(4.5,0){$\hspace{0.3pt} \cdot$} \end{picture}} \newcommand{\circdown} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangledown$} \put(4.5,1.5){\scriptsize $ \circ $} \end{picture}} \newcommand{\circup} {\setlength{\unitlength}{1pt} \begin{picture}(10,8) \put(1,0){$\bigtriangleup$} \put(4.5,1.5){\scriptsize $ \circ $} \end{picture}} \newcommand{\smallcirc} {\setlength{\unitlength}{1pt} \begin{picture}(10,12) \put(5,3){\circle{7}} \end{picture}} \begin{document} \thispagestyle{empty} % first page without page number \begin{center} {\large\bf Some Comments on a Note on } \\[2ex] {\large\bf Fortran, LIA--1, IEEE~754 and Kulisch--Miranker Arithmetic } \\[3ex] {\bf (Fortran document ISO/IEC JTC1/SC22/WG5\,--\,N953, \\[1ex] by Mary Payne, August 31, 1993) \\[4ex] by Ulrich Kulisch and Wolfgang V. Walter \\[1ex] December 31, 1993 } \end{center} The note by Mary Payne addresses an important subject which is central to the whole of numerical computation: the properties of computer arithmetic and their interplay with programming languages. The note is highly relevant to contemporary developments of arithmetic standards and hardware. We would therefore like to comment on it, in particular with respect to what is there called Kulisch--Miranker (K-M) arithmetic. K-M arithmetic has been around for about 20 years. It has often been misinterpreted and misunderstood. Most misunderstandings stem from the fact that K-M arithmetic is based on a clear mathematical theory whereas the usual discussion of computer arithmetic in more colloquial terms generally fails to meet a rigorous mathematical definition. The misinterpretations are mostly of a personal nature. We will not comment on them. K-M arithmetic was essentially developed to enhance the mathematical power of the digital computer. Traditionally, the computer is only capable of computing approximate solutions to a problem. A lot of mathematics may be required to develop an algorithm for such a task and to derive error estimates for the computed results. However, this in itself does not imply that a strict mathematical answer can be deduced because classical error analysis does not take into account all computational errors. Thus, even though approximations are often satisfactory, they may nevertheless be inaccurate or completely wrong in a significant number of cases. With traditional floating-point arithmetic, it is usually very difficult to tell when something has gone wrong simply by looking at the numerical results. In contrast, K-M arithmetic aims to do rigorous mathematics with the computer. For example, rigorous, highly accurate bounds can be computed for the solution of systems of equations or initial, boundary, or eigenvalue problems of ODEs or integral equations. A proof of the existence and uniqueness of the solution within the computed bounds is automatically performed by the computer. This is often referred to as ``automatic result verification'' or ``self-validation of computational results''. Even when used to compute approximations only, K-M arithmetic generally delivers results of higher accuracy than traditional floating-point arithmetic due to its strict mathematical requirements. More importantly, however, K-M arithmetic enables the transition from Numerical Mathematics to Mathematical Numerics. What is K-M arithmetic? Instead of reducing all calculations to the four elementary arithmetic operations for floating-point numbers, K-M arithmetic requires twelve fundamental data types (or mathematical spaces) in a computing environment. These are the four basic data types real, complex, interval and complex interval and the vectors and matrices over these types. All computer operations for these types should be defined by the concept of ``semimorphism'': If $M$ is any one of these twelve spaces and $N$ its computer-representable subset, and if $\circ$ is any arithmetic operation in $M$, then the corresponding computer operation $\qcirc$ in $N$ should be defined by \vspace{1ex} \begin{myequationnew}{(RG)}{a \qcirc b := \quadr(a \circ b)} {for all $a, b \in N$}{(semimorphism)} \end{myequationnew} \vspace{-2ex} where $\quadr: M \rightarrow N$ is a mapping from $M$ onto $N$ (called a rounding) with the following properties: \vspace{1ex} \begin{myequationnew} {(R1)}{\quadr(a) = a}{for all $a \in N$} {(projection)} \end{myequationnew} \vspace{-2ex} \begin{myequationnew} {(R2)}{a \le b ~\Rightarrow~ \quadr(a) \le \quadr(b)} {for $a, b \in M$}{(monotonicity)} \end{myequationnew} \vspace{-2ex} \begin{myequationnew} {(R3)}{\quadr(-a) = - \quadr(a)}{for all $a \in M$} {(antisymmetry)} \end{myequationnew} \vspace{-2ex} This means that every computer operation should be performed in such a way that it produces the same result as if the mathematically correct operation were first performed and the exact result then rounded into the computer-representable subset. This rule is optimal in the sense that there is no better computer-representable approximation to the true result (with respect to the prescribed rounding). At the end of the introduction of the book on Computer Arithmetic by Kulisch and Miranker, it is already stated that this concept of semimorphism should and ``can be used as an axiomatic definition of computer arithmetic in the context of programming languages''. A careful analysis of the requirements is given in the book. All semimorphic computer operations are of 1 ulp accuracy (or even 1/2 ulp accuracy in the case of rounding to nearest). It is ultimately shown that semimorphic operations can be provided on a computer if, on a low level (preferrably in hardware), 15 fundamental operations are available: the five operations $+, -, \,*\,, \,/\,, \,\cdot\,$, each one with the three roundings $\quadr, \bigtriangledown, \bigtriangleup$. Here $\cdot$ means the dot product of two vectors, $\quadr$ is a monotone, antisymmetric rounding (e.~g.\ to nearest) and $\bigtriangledown$ and $\bigtriangleup$ are the monotone downwardly and upwardly directed roundings. All 15 operations $\qcirc, \circdown, \circup$ with $\circ \in \{+, -, \,*\,, \,/\,, \,\cdot\,\}$ are defined by (RG). The IEEE~754 standard prescribes 12 of these 15 operations (for $\circ \in \{+, -, \,*\,, \,/\,\}$), but fails to define the dot product operations, which are the most crucial operations in the common vector spaces. IEEE~754 also prescribes specific data formats. The LIA--1 standard is more general and does not specify any particular data formats or rounding modes. It only requires that the four elementary floating-point operations be accurate to 1~ulp (unit in the last place). As a consequence, interval arithmetic cannot be implemented in a straightforward manner (in contrast to the situation with IEEE~754 arithmetic). Also, addition and subtraction are not required to satisfy property (RG). This unfortunate allowance was apparently made to accomodate /370 arithmetic, which is of 1~ulp accuracy, but whose addition and subtraction are not semimorphic. Mary Payne's note states that ``like IEEE~754, K-M arithmetic can conform to \mbox{LIA--1}''. Since K-M arithmetic specifies the mathematical requirements, the opposite question should be asked: do IEEE~754 and LIA--1 conform to K-M arithmetic. The answer is no in both cases since neither standard provides the dot product operations $\qdot, \dotdown, \dotup\,$. Furthermore, LIA--1 does not require semimorphic addition and subtraction and does not provide the directed roundings $\bigtriangledown$ and $\bigtriangleup\,$. Two serious disadvantages of most existing IEEE processors are that full double-length products cannot be obtained from the outside (even though they are computed internally) and that the operations with directed roundings $\circdown$ and $\circup$ where $\circ \in \{+, -, \,*\,, \,/\,\}$ are not provided as single instructions with the rounding mode incorporated. The former restriction complicates the implementation of accurate complex arithmetic and of accurate dot products unnecessarily whereas the latter slows down interval arithmetic considerably. Many processors need as many machine cycles to set the rounding mode as to perform the rounded arithmetic operation itself. Since in interval calculations, the rounding mode has to be switched frequently, this introduces a severe and unnecessary penalty. A ``Proposal for Accurate Floating-Point Vector Arithmetic'' was drafted by the ``IMACS/GAMM Working Group on Enhanced Computer Arithmetic'' and extensively discussed during the past two years. In its final form, the proposal was unanimously approved and adopted by GAMM and by IMACS in 1993 and is now an official document of these mathematical societies. In essence, it requires K-M arithmetic and gives some hints on its realization. K-M arithmetic has been implemented in hardware, in firmware, and in software on many different platforms and has been available since the early 1980's. The accumulation of products in a long fixed-point register allows an easy realization of the optimal dot product as defined by (RG). Besides being highly accurate, fixed-point accumulation in hardware turns out to be at least as fast as a customary implementation using floating-point operations. Numerical libraries and programming languages which support K-M arithmetic have been available for a number of years (e.~g.\ ACRITH, ACRITH--XSC, PASCAL--XSC, C--XSC, and FORTRAN--XSC). Besides the elementary operations discussed above, multiple-precision (``long'') arithmetic for real and complex numbers and intervals of varying length is also provided. It can easily be implemented via the optimal dot product. Using these programming systems, problem-solving routines with automatic result verification have been developed for a large variety of standard problems of numerical analysis as well as for many applications. The mathematical insight into the fundamental principles of computer arithmetic and the technology to realize them in hardware have been available for many years and should be common knowledge by now. Not to incorporate them into arithmetic standards has proven to be a great hindrance to further progress towards making numerical computations more reliable and towards making computers do real mathematics. Many manufacturers believe that all that is necessary is to implement computer arithmetic according to one of the existing standards. Even though this is a safe approach for the manufacturer, it does not serve the user as well as it could. We hope that forthcoming arithmetic standards will take the necessary steps to turn computers into rigorous mathematical tools. \end{document}