Introduction to Real/Expr

Real/Expr is a set of C++ class libraries to support the precision-driven approach to exact geometric algorithms. The main class that users see is Expr, which captures the set of real algebraic expressions involving the operators +, -, *, /, sqrt() over rational numbers. For most purposes, the user only need to access this class. Our expressions can yield approximate values to any user-specified precision (in relative or absolute terms), and supports error-less comparison of numbers.

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 ]

Precision

The concept of precision is central in our system. A real number x is said to approximate another real number z to relative precision r if | x - z | <= | z | × 2^(- r). We say x approximates z to absolute precision a if | x - z | <= 2^(- a). Finally, we say x approximates z to composite precision p = [ r, a ] if either | x - z | <= | z | × 2^(- r)
or
| x - z | <= 2^(- a) holds. Here, r and a may be infinity (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 ]

The Class BigFloat

BigFloat realizes arbitrary-precision floating-point numbers in the following format:

( 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 ]

The Class Real

Real encompasses a variety of number representations:
machine integers (int, long), machine (double-precise) floating-point numbers (double), integers of arbitrary length (BigInt) and rational numbers (Rational), as well as BigFloat. Currently, we use GNU's Integer and Rational for BigInt and Rational, respectively. Note that BigFloat is a slight anomaly here in that, unlike the other numbers, it represents an interval.

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 ]

The Class Expr

Expr captures a set of algebraic expressions.

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 ]

Real/Expr Package

Real/Expr has the following significant points:

Users can implement the exact algorithms without being constrained by the restrictions caused by fixed-precision arithmetic.
Users may be able to expect better performance than the traditional exact computation tools where all numerical quantities are computed ``exactly''. (Currently, our system is not tuned for high performance.)
Users can deal with algebraic expressions involving the squareroots.

Here are some typical applications of our package:

Under some circumstances, when speed is not an issue or in prototyping algorithms, Real/Expr may be a primary candidate for implementing algorithms. The implementation could be an almost straightforward interpretation of the underlying algorithm.
Machine (nonrobust) floating-point arithmetic is fast. When the robustness (or exactness) needs to be ensured in such an algorithm, the user can embed Real/Expr code only at those critical points in their program where exactness is important, or when some ``filter'' tells them at run-time that machine floating-point computation is insufficient.

[ top of this page ] [ Precision ] [ BigFloat ] [ Real ] [ Expr ] [ Real/Expr Package ]

[ Real/Expr Homepage ]

Should you have any comment, send an e-mail to ouchi@simulation.nyu.edu.