sqrt()
These expressions are based on the class Real. This is a superclass that contains several subclasses of number representations (from native machine numbers to big numbers). One particular subclass, BigFloat plays a special role in our system. Our BigFloat numbers are intended to be approximations for real numbers and has built-in support for maintenance of error bounds.
The system as explained in these notes have been implemented. Its full details are found the thesis Real/Expr : Implementation of an Exact Computation Package.
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]
infty
) (in our system, this means the largest
representable machine long). For instance,
[ r, infty
] specifies a relative precision of
r bits.
Here, r and a may be called the number of absolute and relative bits of precision, respectively. Consider what it means to say that ``x approximates z to one relative bit of precision''. By definition, this means that | x - z | <= ½ | z |. We can immediately conclude from this inequality that x and z have the same sign. This is useful for many applications as noted in our introduction. We can specify such a relative 1-bit approximation bounds in our Real/Expr package.
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]
( mantissa ± error ) × BASE ^ exponent,where mantissa and exponent are integers of arbitrary length and error is a non-negative integer. The triple
x = < mantissa, error, exponent >,viewed as a BigFloat, defines the interval
[ ( mantissa - error ) × BASE ^ exponent, ( mantissa + error ) × BASE ^ exponent ].We say a real number X belongs to the BigFloat x if X lies in this interval. Intuitively, x ``represents'' X. Of course, this representation by x is not unique unless error=0.
What is interesting about the error is that we automatically maintain this error in BigFloat operations. That is, if x, y are BigFloats, and the real numbers X, Y belong to x, y (respectively), then after any operation such as z = x * y, the value X * Y is guaranteed to belong to z. Our algorithms try to minimize the error in z within the constraints of efficiency. If x, y are both error-free, it is also natural to try to make z error-free. But this may be impossible for the division and square-root operations. In this case, error in z is bounded by some default (user-changeable) value.
Our goal is to use BigFloat in an efficient implementation of Real/Expr. Nevertheless, BigFloat but itself has direct application in exact computation (see the paper Basis for Implementing Exact Geometric Algorithms).
Our current implementation of BigFloat is based upon the Integer class from GNU. For efficiency, we make two other restrictions on BigFloat numbers: first, we always truncate error so that it is always representable by a machine unsigned long. Second, we restrict exponet to a machine long.
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]
Over Real, one can perform the operations
+, (unary and binary) -,
*, / and sqrt()
without
causing overflow or underflow. These operations are implemented in an
object-oriented way, that is, given specific operand(s), the compiler
can choose the correct algorithm depending on the type(s) of the
operand(s).
Caveat: most users will not want to directly use Real. They may have to do a considerable amount of book-keeping in order to attain the goal of exact computation. In particular, they need to have an understanding of how to propagate precision in our system which are automatic in Expr.
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]
Formally, an instance of Expr is a rooted DAG where
each leaf can store some rational value and each internal node
represents one of the operations +, (unary and
binary) -, *, / and
sqrt()
. If every leaf of the tree rooted at
Expr e stores a rational value then
e can be viewed as an element of a real algebraically
closed field. (Indeed, it is precisely a constructible real
number.) We call this element the exact value of
e.
Expr e maintains some
Real x and precision p such
that x approximates the exact value of e to
precision p. The precision p is a pair of
integers [ r, a ] whose meaning is explained
above. This p can explicitly set by
the user. For example, the comparison operation e > 0
will set the necessary precision p to determine the sign of
the exact value of e. To get an approximation x
of e to p, we develop precision-driven
algorithms:
we drive the precision top-down from the node e to its
descendent leaves, and collect approximations bottom-up from leaves to
the node e. In this case, the precision of an instance is
set by its parent node.
The semantics of Expr (especially of the assignment operator) is somewhat subtle: see the tutorial and UNIX man page for Expr. This is designed to make the use of our system natural.
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]
[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]