Back to the PSciCo homepage
The Arithmetic Library
Overview
Algorithms that perform some sort of numerical computation are very
often designed with the assumption that the computer they are going to
be executed on has the capability to manipulate exactly arbitrary real
numbers. This is never the case;
a simple cardinality argument shows that the real numbers are not even
all representable within a
computer, given that an input to a computer can be at most countable.
Worse yet, the basic predicates over those reals that are representable
are only semi-decidable.
Thus, this so called Real RAM model of computation is not
realistic, and is actually the main reason for the lack of robustness that
many numerical algorithms exhibit. However, it is very often the case
that the full power of real numbers is not really needed. Many
algorithms will work quite quickly and robustly using floating-point
arithmetic, and reverting to some sort of exact computation in only few
crucial subroutines.
To design a good algorithm then, the programmer has to carefully choose
the numerical library that his problem calls for. With this in mind,
we are designing several numerical libraries of varying speed and
exactness. Some of them include: arbitrary precision floating-point
arithmetic, interval arithmetic, and rational numbers of several
flavors (with and without normalization, with interval filters, etc).
This list should in the future be extended with an implementation of
polynomials over various ordered monoids of power products and with various
coefficients, an implementation of algebraic numbers and an implementation of
computable reals.
Relevant Files