\manpage {floatf} {} {A Floating Point Filter}  
 
\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 $\tilde{E}$ of
the true value $E$ is computed. However, $\tilde{E}$ might still be
able to tell us something about the sign of $E$. If $\tilde{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 $\tilde{E}$ and $E$ 
agree and if $\tilde{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$;
$floatf$s 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$.  
 
\creation x 
 
\create { }
   { introduces a variable \var\ of type \name\ and initializes
              it with zero.  }
 
 
\create {(integer\ i)}
   { introduces a variable \var\ of type \name\ and initializes
              it with integer $i$.  }
 
 
\operations 2 4 
 
\binopfunc  floatf   {a\ +b}
           {  Addition.  }
 
 
\binopfunc  floatf   {a\ -b}
           {  Subtraction.  }
 
 
\binopfunc  floatf   {a\ *b}
           {  Multiplication.  }
 
 
\func  int Sign {( floatf\ f)}
           {  as described above.  }
 
 
\implementation
A $floatf$ is represented by a double (its value) and an error bound.
An operation on $floatf$s 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 
(\cite{Me-Naeher:sweep}).
 
\example
see \cite{Me-Naeher:sweep} for an application in a sweeep line algorithm.

 
