CGAL users discussion list

[Marc Mörig <>]

Dear Sebastien,

as major part of my still ongoing PhD thesis I have implemented an exact 
number type, which I call RealAlgebraic, that supports + - . / and n-th 
roots. Like leda::real or CORE::Expr it stores arithmetic expressions in 
a dag, and, to compute their sign, evaluates them with increasing 
accuracy and decides that numbers are zero using separation bounds.

RealAlgebraic allows to exchange some of the major parts any such number 
type must have, you can for example use either leda::bigfloat or mpfr 
arithmetic as the workhorse behind the scenes. It furthermore employs 
exact computations with hardware floating-point numbers. These 
techniques require the default rounding mode to be set, but are entirely 
optional.

I have run a few experiments using algorithms from cgal (2D Delaunay 
Triangulation, homogeneous and Cartesian segment intersection, 
arrangements of circles, and Voronoi diagrams of segments) and can say 
that so far RealAlgebraic is a major improvement over leda::real and 
CORE::Expr. For arrangements of circles it comes close to what I call 
static algebraic predicates, i.e. predicates involving algebraic numbers 
of small degree based on static sturm sequences and similar techniques. 
For Voronoi diagrams of segments it clearly outperforms static algebraic 
predicates.

Of course there is the problem of selection bias in my experiments, that 
is why I would like to add at least one 'real world' application.

There is some code available at
http://wwwisg.cs.uni-magdeburg.de/ag/RealAlgebraic/
but it is over a year old. I intend to update that site soon, but need 
to add better installation support first. If you want to try 
RealAlgebraic yourself please ask me and I will provide you with a copy.

Marc

On 04/02/2013 07:21 AM, Sebastien Loriot (GeometryFactory) wrote:
> What is "your number type"?
>
> Sebastien.



--
Marc Mörig                                 Email:  

Institut für Simulation und Graphik        Phone: +49 391 67-52858
Otto-von-Guericke Universität Magdeburg    Office:         G29-227