A Floating Point Filter ( floatf )

Definition

The type floatf provides a clean and efficient way to approximately compute with large integers. Consider an expression E with integer operands and operators + , -, and *, and suppose that we want to determine the sign of E. In general, the integer arithmetic provided by our machines does not suffice to evaluate E since intermediate results might overflow. Resorting to arbitrary precision integer arithmetic is a costly process. An alternative is to evaluate the expression using floating point arithmetic, i.e., to convert the operands to doubles and to use floating-point addition, subtraction, and multiplication.

Of course, only an approximation E' of the true value E is computed. However, E' might still be able to tell us something about the sign of E. If E' is far away from zero (the forward error analysis carried out in the next section gives a precise meaning to "far away") then the signs of E' and E agree and if E' is zero then we may be able to conclude under certain circumstances that E is zero. Again, forward error analysis can be used to say what `certain circumstances' are.

The type floatf encapsulates this kind of approximate integer arithmetic. Any integer (= object of type integer) can be converted to a floatf; floatfs can be added, subtracted, multiplied, and their sign can be computed: for any floatf x the function Sign(x) returns either the sign of x (-1 if x < 0, 0 if x = 0, and +1 if x > 0) or the special value NO$\_$IDEA. If x approximates X, i.e., X is the integer value obtained by an exact computation, then Sign(x)! = NO$\_$IDEA implies that Sign(x) is actually the sign of X if Sign(x) = NO$\_$IDEA then no claim is made about the sign of X.

#include < LEDA/floatf.h >

Creation

floatf	x	introduces a variable x of type floatf and initializes it with zero.
floatf	x(integer i)	introduces a variable x of type floatf and initializes it with integer i.

Operations

floatf	a + b	Addition.
floatf	a - b	Subtraction.
floatf	a * b	Multiplication.
int	Sign(floatf f)	as described above.

Implementation

A floatf is represented by a double (its value) and an error bound. An operation on floatfs performs the corresponding operation on the values and also computes the error bound for the result. For this reason the cost of a floatf operation is about four times the cost of the corresponding operation on doubles. The rules used to compute the error bounds are described in ([59]).

Example

see [59] for an application in a sweep line algorithm.