%-*- mode:latex -*-
\documentstyle[12pt]{article}
\textwidth 6.5 truein
\oddsidemargin 0.0 truein
\evensidemargin 0.0 truein
\topmargin -0.75 truein
\textheight 9.0in
\title{FP98: Rounding Modes from the Language Perspective--I}
\author{Richard Fateman\\
Computer Science Division, EECS Dep't\\
University of California at Berkeley}
%date will be placed here automatically
\begin{document}
\maketitle
\begin{abstract}
We justify the use of rounding modes from a language
perspective. (30 mins)
\end{abstract}
\section{Prerequisites}
We assume familiarity with the directed
roundings of IEEE 754.
\section*{Modes, Flags}
It is easy to be confused on this:
\begin{enumerate}
\item Modes are set by the program (rounding, trap enabling)
\item Flags are set as a side effect of an operation
(floating-point overflow)
\end{enumerate}
An overly simplistic view is that modes are read/write
variables to a program, and flags are read/clear variables.
We defer fuller discussion of modes of (for example) enabling traps
and flags and how they fit in to a linguistic framework to
an afternoon session.
In this segment we will deal only with modes
for rounding ToNEAR, ToZERO, ToPOSV, ToNEGV, and how these might
be used, and how this might interact with languages.
\section{Why bother?}
More specifically
{\bf Why would one want a language to support different roundings? }
At least two reasons.
\subsection{On Principle} It is wrong on principle to deny the programmer in
a higher-level language access to ANY computational facility built in
to the hardware. Not only are floating-point concepts
cut out by some languages, nearly all omit some other
useful items like the 32x32 full 64 bit integer multiply
(or 64x64 to 128 bit where available). If we don't make
a fuss now, the argument might even come around to
``why not leave it out of the hardware; it is impossible
to access from software?''
Since it is widely regarded as perverse and counterproductive to
require programmers to write in assembly language, {\em language
designers who (in effect) forbid the use of available features must
have had something in mind.}
{\bf Or did they?} It appears if they
thought about it at all, what they had in mind was that those
features were useless.
Or useful only to numerical experts who
somehow would not mind writing in assembly language(!?) Or violated
portability constraints (more tomorrow about this).
Or that the language designer could make the best choice for all users.
Or that the language designer should leave these issues as
platform-dependent or implementation-dependent {\em thereby
promoting chaos, the ultimate goal of computer scientists.}
\subsection{A few plausible general reasons}
(i) investigating numerical instability (cf. Javahurt p 57 et seq),
(ii) running various programs (cf. Borneo spec. polynomial
evaluation) that make sense rounding up and down.
and (iii) interval arithmetic, discussed below.
\subsubsection{Interval Arithmetic}
Instead of the conventional representation of a real number by
an approximation: the nearest exact floating-point number,
represent a real number by TWO fp numbers: a lower and an
upper bound.
A large body of literature with many variations
has emerged on numerical computing
with real intervals. This describes
operations on such numbers (+,*,/, and more
elaborate ones such as elem. transcendental functions,
Newton iteration-based root-finding, etc. are possible.)
Sample rules:
{\tt [a,b] + [c,d] = [a+c, b+d] }
{\tt[a,b] * [c,d] = [ min(a*c, a*d, b*c, b*d), max(a*c, a*d, b*c, b*d)]}
To do this right, in the lower bound calc. we round all ops ToNEGV,
and in the upper bound calc., round all ops ToPOSV.
Careful programs can produce results
with guaranteed [but rarely tight] error bounds. We are in
an era when a factor of 4 or even 10 in speed and a factor
of 2 in memory may be a fair trade for some assurance that
the result is not totally bogus.
{\bf Aside:}
Can you simulate rounding modes without hardware support?
If you assumed that all operations were accurate to within
1/2 ULP, then one could ``round directionally after the fact'' by taking the
nearly correct answer and adding or subtracting 1 ULP, thereby
getting a lower or upper bound for sure. This is
slow and not a good idea for interval arithmetic.
\begin{enumerate}
\item Software up/down rounding doubles the
width of the interval that you'd get by directed rounding of
a single operation on a float format; this may not seem so bad, but
the width of intervals tend to grow exponentially with the
number of operations so you'd
like to not contribute to this phenomenon. (not a big deal).
\item Software post-rounding
is likely to be slower than hardware rounding. (bigger deal).
\item The real
problem may be that your calculations may involve exact numbers
(say, perfectly representable integers,or such numbers multiplied
by powers of two)
in which high=low=exact, and adding +-ULP (unit in the last place)
is a far more substantial fudge than is justifiable. (Later we will
talk about ``How much is accuracy worth?)
\end{enumerate}
\subsubsection{An Example}
Let's consider plotting
\begin{verbatim}
sin(1/x) -1<=x<=1.
\end{verbatim}
Near {\tt x= 0}, a naive plotting program based on sampling
at fixed intervals (say every 0.001) will give us a plot which is
effectively a collection of random numbers between -1 and 1.
This is a poor (unfaithful) description of the function.
Consider plotting the Intervals {\tt sin(1/[x,x+0.001])} instead.
This means drawing the rectangles of appropriate height (and width 0.001)
that enclose the points. This looks like a solid mass near
x=0. This is right.
\begin{verbatim}
(pictures: http://http.cs.berkeley.edu/~fateman/plotx.html)
\end{verbatim}
The example is written rather simply with Mathematica, a
language that supports an Interval data type (it took several
revisions of Mathematica to get it almost right.
Now it rounds up and down so
that {\tt 1/Interval[{3.0,3.0}]} is
{\tt Interval[{0.3...32, 0.33...34}]}.
Can you guess its answer for {\tt Sin[Interval[{1.0d60,1.0d60}]]}?.)
%returns Interval [{-1,1}].
\end{document}