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

• XFLOAT: Arbitrary precision floating point
• EXTENDED_FLOAT: Routines for manipulating arbitrary precision floating point numbers
• XFloat.sml
• ExtendedFloat
• RATIONAL: Rational numbers
• NormalizedRational: Fractions with mutually prime numerators and denominators
• UnNormalizedRational: Normalization strategy can be selected in run-time
• RoundDownLazyRational: Fractions are approximated by a float interval. The predicates are performed exactly only if the result cannot be infered using only interval arithmetic.
• RoundDownFilteredRational: Another implementation of lazy rationals
• FLOAT_INTERVAL: Arithmetic over intervals with floating point bounds
• RoundDownFloatInterval
• NUMBER_THEORY: Routines for manipulating infinite integers
• InfiniteInteger: Extension of the standard basis IntInf structure
• NumberTheory: For now only gcd and some helper functions
• Compiler: A small compiler for automatic generation of adaptive and staged floating point code from exact source aritmetic expressions [Note: requires Table library and the rest of the arithmetic library]
• COMPILE: Signature for the compiler
• SOURCE: Source language for the compiler
• TARGET: Target language for the compiler
• Parser
• Ulps: Symbolic operations over machine epsilon

• Acknowledgements

The PSCICO project is supported by NSF under the title "Advanced Languages for Scientific Computation Environments" as part of the Experimental Software Systems program within CISE. The grant number is 9706572.

Back to the PSciCo homepage.