arithmetic with exact rounding, etc
Jim White
mathimagics at yahoo.co.uk
Sat Apr 8 13:21:36 CEST 2006
As I understand it, "Exact arithmetic" is a
methodology, an attempt to systematically address the
fundamental problems of error propagation ithat are
inherent in all floating-point computations,
irrespective of precision. You might say it's an
approach to the intrinsic problem of "coping with
inexactness" :-)
Any "Computational Science" text will usually begin
with a review of the nature of rounding errors and
cancellation errors in floating-point arithmetic, and
a simple overview should be locatable that way (eg
Michael T. Heath, "Scientific Computing", McGraw Hill,
2002). (ComptlSci is simply the current term for what
we used to call Numerical Analysis, so any old NA text
wold also be worth a look)
In a nutshell, these issues become more and more
complex as the computations you want to perform become
more complicated.
The errors involved in the basic arithmetic operations
are easily predicted, but when you take a more complex
calcaultion such as the evaluation of a function like
the natural logarithm, then things become very
complicated indeed, as typically a single evaluation
will involve thousands, perhaps millions, of basic
arithmetic operations.
Predicting the error propagation profile (will the
errors propagate? compensate? or simply mislead?) and
thereby predicting behaviour of such calculations is
complicated (affected as it is by the nature of the
algorithm, the actual data parameters being used, the
underlying arithmetic support, etc).
This sort of analysis is also necessary if one wishes
to rigorously prove the behaviour and/or precision of
certain computations. A systematic approach to
rounding is clearly of benefit there. (MPFR have a
document in which they systematically prove the
accuracy and error behaviour of many of their
functions).
There are other approaches - "interval arithmetic", in
which one operates with calculations that can be
proved to be correct within a given (selectabl
usually) interval.
"Guard digits", on the other hand, is one specific and
reasonably effective way of approaching less
complicated computation.
When you think a series of basic operations at a given
precision might not yield a result with the desired
accuracy, then you can often compensate for this by
simply performing all intermediate calculations at a
slightly higher precision, and then truncating the
result to the desired precision. (Imagine your
electronic calculator as having a few extra digit
positions that aren't displayed, but help it to ensure
that the rightmost digit you DO see is correct, or
should I say, predictably rounded!
GMP itself doesn't have to deal with these problems,
really, because it's only concerned with those basic
operations (in floating-point mode). Their error
behaviour is well known, and easily managed.
Jim White
ANU
More information about the gmp-discuss
mailing list