%-*- 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{The Language View: Expression Evaluation in Mixed Precision}
\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}
This section consists of draft Notes on language and compilers. Here
we address the issue of what compilers should be allowed to
do, encouraged to do, and what should be forbidden.
\end{abstract}
\section{Prerequisites}
We assume that the audience is familiar
with the IEEE 754 standard for binary floating-point arithmetic,
and has familiarity with at least one high-level numerically-oriented
programming language (Fortran or C most likely).
{\section {Expression evaluation with mixed precisions (etc)}
We've previously discussed licensing of optimization
to deal with mixed precisions: What should the license
allow, and what makes sense?
How much work is it to implement various policies?
The issue may be top-down vs bottom up domain inference;
widening / coercing downward.
The traditional compiler dichotomy for this
is Inherited attributes vs. Synthesized attributes.
\subsection{Precisions from a fixed set}
Here are some possible rules
\begin{itemize}
\item[(i)] If a and b are of different widths, say a wider than b,
{\tt c := a + b} is done by converting b to width a, and adding, then
storing (perhaps narrowing or widening) to width of c.
\item[(ii)] if a and b are of widths less than c,
{\tt c := a + b} is done by converting a and b to the width of c, adding, then
storing in c.
\item[(iii)] Regardless of the widths of a, b, and c,
{\tt c := a + b} is done by adding in the machine's widest format, then
storing (perhaps narrowing) in c.
\item[(iv)] Require everything that is not obvious
to be explicit, e.g. something like
\begin{verbatim}
storeasdouble
(&c, doubleadd(coercetodouble(a),
coercetodouble(b)))
\end{verbatim}
\item[(v)] Runtime untyped variables,
but typed-value system. Variables like a, b, c have
no types, but every number value has a type. Compute the appropriate
type of each operation at runtime, as needed. This would have
to be entirely by synthesized attribute (bottom up) since the
names would not have types (though they might have previous
values).
\item[(vi)] Method dispatch deferred to runtime
(fully ``dynamic object-oriented'' approach)
{\tt c := A+B} is treated as
\begin{verbatim}
assign(&c,
add(a,b,type-of-a,type-of-b,type-of-c)
,type-of-c)
\end{verbatim}
In this case the {\tt add} function looks at all the types
and chooses the right method, and the assign function looks
at all the types as well. What is implemented depends entirely
on how the functions (or ``methods'') for assign and add are
defined, and also what the actual values of a and b are.
\end{itemize}
The old C rules were (iii). This is better than (i), but perhaps
wasteful compared to (ii) which is hardly ever (never) done.
Rule (iv) has the advantage of allowing for the possibility that
a low precision input to a function may in fact give a high
accuracy answer. Log(1.0[+-.1]*10e600) is a low precision input,
uncertain even in its 2nd decimal digit,
but the answer is 1385.55+-0.09, correct to about 5 decimal places.
Rule (v) is usually available only in interpreted languages with
a very loose or non-existent type system. If used to full
generality, it is not efficient in time or space since numbers have to be
tagged as to length (etc), and repeatedly checked.
Rule (vi) is very flexible and probably slower than one
would like, unless the generality can be compiled away
either in a pre-pass or a ``JIT'' system. [Another idea
Java took from Lisp, by the way]
{\center{\bf IS THERE A WAY TO DO THIS RIGHT?}}
{\bf Figuring out the best width for preserving what appears
to be the most reasonable precision intended by a computation
may require from the compiler, two passes over an expression.
This allows
propagation upward and downward in an expression tree.}
This is
not an intolerable burden for a compiler, and in fact some
languages (Ada) already require this kind of activity.
If methods are overloaded, there is a potential
for additional scans to achieve method resolution.
\begin{quote}
By themselves, numbers possess neither precision nor accuracy. In
context, a number can be less accurate or ( like integers ) more
accurate than the precision of the format in which it is
stored....
What matters in floating-point computation is how closely
a web of mathematical relationships can be maintained in the face of
roundoff, and whether that web connects the program's output
strongly enough to its input no matter how far the web sags in
between....
\end{quote}
from ``Java Hurts'' (Kahan/Darcy)
\subsection{Variable precisions}
Not all systems are limited to a few fixed precisions.
\subsubsection{Rational}
Exact rational arithmetic (1/2+1/3 = 5/6) is available in ``computer
algebra systems'' (CAS) like Mathematica, Maple, Macsyma, and
a dozen less well-known systems. Rationals don't solve
0/0 problems, but over/underflow, and inexact cannot happen
under algebraic operations. But slow, and not closed
under elementary functions. But one could convert any
ordinary float to an exact rational number: fraction * power
of two, and compute +, *, / EXACTLY!
This is usually not considered practical because of inefficiency,
but such tools can be used to prove mathematics computationally.
\subsubsection{Arbitrary-precision floats}
Variable (high) precision arithmetic: CAS have these, but
you may also just use Fortran or C subroutines:
MPFUN (D. H. Bailey) is only the most recent of a sequence
of library packages to support
\begin{itemize}
\item n-digit floats, n being
a parameter;
\item an exponent range huge enough to make
over/under flow extremely rare (say, 32 bit exponent)
\end{itemize}
Designs like MPFUN tend to present (at least in their
design) new explicit choices that were more easily
settled for fixed precisions.
E.g. SIN( argument, precision-of-result, value-of-pi)
where value of pi is needed for argument reduction.
(Fortran also may force
other silly global choices ``max precision for this run of
MPFUN'' compiled into COMMON)
\subsubsection{Target precision}
Accuracy-goal-driven interval-based computations:
``Evaluate this expression to a value with relative error less than R.''
Assume you can bump up the precision of all inputs, the
expression is suitably continuous and differentiable, and
you can implement all needed routines in interval arithmetic
to arbitrary precision.
Try it with precision p. If you
fail to meet the accuracy requirement, try precision 2*p.
etc.
Mathematica seems to have some fuzzy claims about trying
to do this for ``any'' evaluation;
Many library routines exist for targeted accuracy (say, for
quadrature, zerofinding, etc).
\subsection{Treatment of domains}
Widening not only affects the notion of precision,
but also, in a different sense, of domains.
What should sqrt(-1) be? distinguishing between sqrt(x:real) from
sqrt(z : complex) means that sqrt(-1) is an error, but sqrt( -1+0i) is
i.
IEEE 754 is not prescriptive with respect
to all issues of numerical interest(most esp. wrt complex numbers,
but also transcendental functions, etc.). Even within its scope
it does not prevent programmers or language designers
from setting strange policies.
Example of a questionable default:
Common Lisp makes sqrt(-1) into a complex
result, thereby invalidating compiler optimizations
that deduce the type of sqrt(x) from the type of x.
}
\section{How accurate is enough, a question of philosophy}
{
There is a pervasive and generally useful notion that is popular
among application programmers that if you run a complicated
floating-point calculation and are unsure if the answer is
correct, a simple check may be available: If a higher precision
version of the program can be run, try it. If you get the
same answer in single as well as double, then it is probably
correct. Or double and quad, etc. While this can be
merely signal agreement to the wrong answer, why are we
not happy with it?
(Followed to its logical conclusion as has been done by
some hardware designers, one finds many niceties
eliminated. Who cares if the results are entirely accurate; if
it matters, the computation will be re-done to higher precision
and in wider exponent range arithmetic.
Sloppy division, rounding incorrectly, cavalier treatment
of underflow, imprecise interrupts can all be excused in the
name of speed.)
Why should we care? It depends on who is meant by
``we''.
An engineer needing a one-off solution of a problem
that is in the middle of a very well-conditioned
problem might not care, {\em except that he might be wrong and
his problem is on some border (or his program is unstable)}.
We as suppliers of supposed quality hardware and software
should care [ref:WK's {\em Matlab's Loss is Nobody's Gain}]
When one is constructing software for re-use by others (libraries,
interactive engineering packages etc), then one cannot put
a cost on inaccuracy.
In particular, the numerical software ``engineer'' cannot generally
judge for users of some library
\begin{itemize}
\item Where less accuracy is acceptable (context unknown);
\item How (in)accuracy might be magnified by subsequent use;
\item How inaccuracy might be associated with risk.
\end{itemize}
Purveyors of software and hardware must protect the (relatively
speaking) naive users from excessively inaccurate computation.
``Kahan's Law on Precision''
\begin{verbatim}
An increase of K significant bits in an intermediate result's accuracy
decreases by 2^(-K) the incidence of numerical embarrassment
attributable to the later use of that result.
\end{verbatim}
}
\end{document}