/*******************************************************************************
+
+  LEDA 3.5
+
+  real.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

/* This file has been automatically generated from "real.w"
   by CTANGLE (Version 3.1 [km2c]) */

#ifndef LEDA_REAL_H
#define LEDA_REAL_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350117
#include <LEDA/REDEFINE_NAMES.h>
#endif


/*{\Manpage {real} {} {The data type real}
}*/

/*{\Mdefinition
An instance $x$ of the data type \Mtype is an algebraic real number.
There are many ways to construct a \Mtype:
either by conversion from |double|, |bigfloat|, |integer| or |rational|
or by applying one of the arithmetic operators $+, -, *, /$ or $\sqrt[d]{} $ to
\Mtype numbers.
One may test the sign of a \Mtype number or compare two \Mtype numbers by
any of the comparison relations $=, \neq, < , \leq, >$ and $\geq$.
The outcome of such a test is {\em exact}.
There is also a non--standard version of the sign function: the call
|x.sign(integer q)|
computes the sign of |x| under the precondition
that $\Lvert x\Lvert \leq 2^{-q}$ implies $x = 0$.
This version of the sign function allows the user to assist the data type in the
computation of the sign of $x$, see the example below.

There are several functions to compute approximations of \Mtype{s}.
The calls |to_bigfloat(x)| and |x.get_bigfloat_error()| return |bigfloat|s
$xnum$ and $xerr$ such that $\Lvert xnum - x \Lvert \leq xerr$.
The user may set a bound on $xerr$.
More precisely, after the call |x.improve_approximation_to(integer q)| the
data type guarantees $xerr \leq 2^{-q}$.
One can also ask for |double| approximations of a real number $x$.
The calls |to_double(x)| and |x.get_double_error()| return |double|s $xnum$ and
$xerr$ such that $\Lvert xnum - x \Lvert \leq  \Lvert xnum \Lvert * xerr$.
Note that $xerr = \infty$ is possible.
}*/

#include <LEDA/bigfloat.h>
#include <LEDA/rational.h>
class real_rep;
class real
{

double value;
real_rep*PTR;
bool is_double;


void adjust()const;


public:


/*{\Mcreation x
}*/

/*{\Mtext
\Mtype{s} may be constructed from data types |double|, |bigfloat|,
 |long|, |int| and |integer|.
 The default constructor |real()| initializes the \Mtype\ to zero.
}*/

real();
real(double);
real(int);
real(const integer&);
real(const bigfloat&);
real(const rational&);
real(const real&);
real(real_rep&);

~real();

real&operator= (const real&);

/*{\Moperations 1.7 3.5
}*/
/*{\Mtext \settowidth{\typewidth}{|bigfloat|}
          \addtolength{\typewidth}{\colsep}
          \computewidths
}*/


friend double to_double(const real&);
/*{\Mfunc returns the current double approximation of \Mvar.
}*/

double to_double()const;

friend bigfloat to_bigfloat(const real&);
/*{\Mfunc returns the current bigfloat approximation of \Mvar.
}*/

bigfloat to_bigfloat()const;

double get_double_error()const;
/*{\Mop returns the relative error of the current double approximation
    of \Mvar, i.e.,
    $\Lvert |x-to_double(x)|\Lvert$
    is bounded by
    $\mbox{|x.get_double_error()|} \cdot \Lvert \mbox{|to_double(x)|} \Lvert$.
}*/

bigfloat get_bigfloat_error()const;
/*{\Mop returns the absolute error of the current bigfloat approximation of
   |x|, i.e., $\Lvert\mbox{|x-to_bigfloat(x)|} \Lvert$ is bounded by
    $\mbox{|x.get_bigfloat_error()|}$.
}*/

friend int sign(const real&x);
/*{\Mfunc returns the sign of (the exact value of) \Mvar.
}*/

int sign()const;

int sign(const integer&q)const;
/*{\Mop as above. Precondition: if $\Lvert \mbox{x} \Lvert  \leq  2^{-q}$
   then $\mbox{x} = 0$.
}*/

int sign(long)const;

void improve_approximation_to(const integer&q)const;
/*{\Mopl (re-)computes the approximation of \Mvar\ such that
  $\mbox{|x.get_bigfloat_error()|} \leq 2^{-q}$
  after the call
  |x.improve_approximation_to(q)|.
}*/

void compute_with_precision(long k)const;
/*{\Mopl (re-)computes the approximation of \Mvar; each numerical operation
   is carried out with $k$ binary places.
}*/

void guarantee_relative_error(long k)const;
/*{\Mopl (re-)computes an approximation of \Mvar\ such that the relative error
    of the approximation is less than $2^{-k}$.
}*/

friend ostream& operator<<(ostream&O,const real&x);
/*{\Mbinopfunc writes the closest interval that is known to contain $x$
    to the output stream $O$
}*/

friend istream& operator>>(istream&I,real&x);
/*{\Mbinopfunc reads |real| number |x| from the output stream $I$
   (in |double| format)
}*/



friend real operator+(const real&,const real&);
friend real operator-(const real&,const real&);
friend real operator*(const real&,const real&);
friend real operator/(const real&,const real&);
friend real operator-(const real&);

friend real sqrt(const real&x);
/*{\Mfunc $\sqrt{x}$
}*/
friend real root(const real&x,int d);
/*{\Mfunc $\sqrt[d]{x}$, precondition: $d \geq 2$
}*/



friend bool operator<(const real&,const real&);
friend bool operator<=(const real&,const real&);
friend bool operator>(const real&,const real&);
friend bool operator>=(const real&,const real&);
friend bool operator==(const real&,const real&);
friend bool operator!=(const real&,const real&);



LEDA_MEMORY(real)
};

inline int compare(const real&x,const real&y)
{return(x-y).sign();}
inline char*leda_tname(const real*)
{return"real";}




real operator+= (real&x,const real&y);
real operator-= (real&x,const real&y);
real operator*= (real&x,const real&y);




real abs(const real&x);
/*{\Mfunc absolute value of |x|
}*/
real sqr(const real&x);
/*{\Mfunc square of |x|
}*/
real dist(const real&x,const real&y);
/*{\Mfunc euclidean distance of vector (x,y) to the origin
}*/
real powi(const real&x,int n);
/*{\Mfunc |n|.th power of |x|
}*/

/*{\Mimplementation

A \Mtype\ is represented by the expression which defines it and a |double|
approximation $\hat{x}$ together with a relative error bound
$\epsilon_{x}$.
The arithmetic operators $+, -, *, \, \sqrt[d]{}$ take constant time.
When the sign of a \Mtype\ number needs to be determined, the data type first
computes a number $q$, if not already given as an argument to |sign|, such that
$\Lvert \mbox{\Mvar} \Lvert \leq 2^{-q}$ implies $x = 0$.
The bound $q$ is computed as described in \cite{Mignotte:Buch}.
%The data type then computes a bigfloat approximation $xnum$ for \Mvar\ with
%error bound $xerr \leq 2^{-q}$.
%The sign of $xnum$ is then returned as the sign of \Mvar.
Using |bigfloat| artihmetic, the data type then computes an interval $I$ of
maximal length $2^{-q}$ that contains \Mvar.
If $I$ contains zero, then \Mvar itself is equal to zero.
Otherwise, the sign of any point in $I$ is returned as the sign of \Mvar.

Two shortcuts are used to speed up the computation of the sign.
Firstly, if the |double| approximation already suffices to determine the sign,
then no |bigfloat| approximation is computed at all.
Secondly, the |bigfloat| approximation is first computed only with small precision.
The precision is then doubled until either the sign can be decided (i.e.,
if the current approximation interval does not contain zero) or the full
precision $2^{-q}$ is reached.
}*/

/*{\Mexample
We give two examples of the use of the data type \Mtype.
The examples deal with the Voronoi diagram of line segments and the intersection
of line segments, respectively.

The following incircle test arises in the computation of Voronoi diagrams of
line segments \cite{Burnikel:thesis, BMS:ESA}.
For $i$, $1 \leq i \leq 3$, let $l_i : a_i x + b_i y + c_i = 0$ be a line
in two--dimensional space and let $p = (0,0)$ be the origin.
In general, there are two circles passing through $p$ and touching $l_1$ and
$l_2$.
The centers of these circles have homogeneuos coordinates $(x_v,y_v,z_v)$, where
\begin{eqnarray*}
x_v & = & a_1 c_2 +a_2 c_1 \pm\mbox{sign}(s)\sqrt{2 c_1 c_2 (\sqrt{N} + D)} \\
y_v & = & b_1 c_2 +b_2 c_1 \pm\mbox{sign}(r)\sqrt{2 c_1 c_2 (\sqrt{N} - D)}
\\[2mm]
z_v & = & \sqrt{N} - a_1 a_2 - b_1 b_2
\end{eqnarray*}
and
$$
\begin{array}{cccccc}
s & = & b_1 D_2 - b_2 D_1, &
N & = & (a_1^{2} + b_1^{2}) (a_2^{2} + b_2^{2}) \\[3mm]
r & = & a_1 D_2 - a_2 D_1, &
D & = & a_1 a_2 - b_1 b_2.
\end{array}
$$
Let us concentrate on one of these (say, we take the plus sign in both cases).
The test whether $l_3$ intersects, touches or misses the circle amounts to
determining the sign of
\begin{eqnarray*}
E := dist^{2}(v,l_3) - dist^{2}(v,p) =
     \frac{(a_3 x_v + b_3 y_v + c_3)^2}{a_3^2 + b_3^2} - (x_v^2 + y_v^2).
\end{eqnarray*}
The following program computes the sign of
$\tilde{E} := (a_3^2 + b_3^2) \cdot E$ using our data type \Mtype.

\def\rsp{\hspace*{5pt} {\bf real}}
\def\sp{\hspace*{5pt}}
\def\lsp{\hspace*{14pt}}

\begin{quote}
{\small
{\bf int} {\sc incircle}(
{\bf real} $a_1$, {\bf real} $b_1$, {\bf real} $c_1$,
{\bf real} $a_2$, {\bf real} $b_2$, {\bf real} $c_2$,
{\bf real} $a_3$, {\bf real} $b_3$, {\bf real} $c_3$
) \\
\{\\
\rsp\ $RN = \mbox{\small sqrt}((a_1*a_1+b_1*b_1)*(a_2*a_2+b_2*b_2))$;\\
\rsp\ $RN_1 = \mbox{\small sqrt}(a_1*a_1+b_1*b_1);$\\
\rsp\ $RN_2 = \mbox{\small sqrt}(a_2*a_2+b_2*b_2);$\\
\rsp\ $A = a_1 * c_2 + a_2 * c_1;$\\
\rsp\ $B = b_1 * c_2 + b_2 * c_1;$\\
\rsp\ $C = 2 * c_1 * c_2;$\\
\rsp\ $D = a_1 * a_2 - b_1 * b_2;$\\
\rsp\ $s = b_1 * RN_2 - b_2 * RN_1;$\\
\rsp\ $r = a_1 * RN_2 - a_2 * RN_1;$\\
\hspace*{5pt} {\bf int} $sign_x = \mbox{sign}(s);$\\
\hspace*{5pt} {\bf int} $sign_y = \mbox{sign}(r);$\\
\rsp\ $x_v = A + sign_x * \mbox{\small sqrt}(C*(RN+D));$\\
\rsp\ $y_v = B - sign_y * \mbox{\small sqrt}(C*(RN-D));$\\
\rsp\ $z_v = RN - (a_1*a_2+b_1*b_2);$\\
\rsp\ $P = a_3 * x_v + b_3 * y_v + c_3 * z_v;$\\
\rsp\ $D_3^2= a_3 * a_3 + b_3 * b_3;$\\
\rsp\ $R^2= x_v * x_v + y_v * y_v;$\\
\rsp\ $E = P*P - D_3^2 * R^2;$\\
\hspace*{5pt} {\bf return} $\mbox{sign}(E)$;\\
%\hspace*{5pt} {\bf return} $E.\mbox{sign}(24*k+26)$;\\
\}
}

\end{quote}
We can make the above program more efficient if all coefficients
$a_i, b_i$ and $c_i$, $1 \leq i \leq 3$, are $k$ bit integers, i.e.,
integers whose absolute value is bounded by $2^k -1$.
In \cite{Burnikel:thesis,BMS:ESA} we showed that for $\tilde{E} \neq 0$
we have $\Lvert\tilde{E}\Lvert \geq 2^{-24k-26}$.
Hence we may add a parameter |int k| in the above program and replace
the last line by
$${\bf return} \; E.\mbox{sign}(24*k+26).$$
Without this assistance, |real|s automatically compute a weaker bound of
$\Lvert\tilde{E}\Lvert \geq 2^{-56k-161}$ for $\tilde{E} \neq 0$
by \cite{BMFS:SODA97}.

We turn to the line segment intersection problem next.
Assume that all endpoints have $k$--bit integer homogeneous coordinates.
This implies that the intersection points have homogeneous coordinates
$(X,Y,W)$ where $X,Y$ and $W$ are (4 k + 3) - bit integers.
The Bentley--Ottmann plane sweep algorithm for segment intersection
\cite{Me-Naeher:sweep} needs to sort points by their $x$--coordinates, i.e.,
to compare fractions $X_1 / W_1$ and $X_2 / W_2$ where $X_1, X_2, W_1, W_2$
are as above.
This is tantamount to determining the sign of the $8 k + 7$ bit integer
$X_1 * W_2 - X_2 * W_1$.
If all variables $X_i, W_i$ are declared {\bf real} then their sign
test will be performed quite efficiently.
First, a |double| approximation is computed and then, if necessary,
|bigfloat| approximations of increasing precision.
In many cases, the |double| approximation already determines the sign.
In this way, the user of the data type |real| gets the efficiency of a
floating point filter \cite{Fortune-vWijk,Me-Naeher:IFIP94} without
any work on his side.
This is in marked contrast to \cite{Fortune-vWijk,Me-Naeher:IFIP94} and
will be incorporated into \cite{Me-Naeher:sweep}.

%-----------------------------------------------------------------------------
% real_header.w
%-----------------------------------------------------------------------------

}*/



#if LEDA_ROOT_INCL_ID == 350117
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif


#endif



