Side effects

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Side effects

Stefan Witzel
Hi again,

I am working with a Hyperbolic Delaunay triangulation, more specifically with a

CGAL::Hyperbolic_Delaunay_triangulation_2<CGAL::Hyperbolic_Delaunay_triangulation_traits_2<>>
dt

Now I'm experiencing the following behavior: I have a program (and a
set of input) that finishes "immediately" but if I add some code, it
takes on the order of minutes and more *even in the old part of the
code*. So clearly there is some side effect, and I'm pretty certain
that I'm not producing it (the only thing I'm passing around is
const). For all I can tell the output (of the old part of the code) is
exactly the same as before so the side effect is restricted to
runtime.
So I'm wondering: is it possible that previous calculations performed
with dt affect future calculations? I'm imagining something like if
some calculation needed a certain precision (or number field), the
consecutive calculations are performed with the same precision even
though they might not need it. If this is the case, is there a way to
"reset" the precision?

Best,
Stefan

P.S.: In case someone has read the previous posts and is wondering: at
the moment I can't get the circular kernel to work because I don't
know how to turn a Hyperbolic_Voronoi_point_2 into a
Hyperbolic_point_2.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Side effects

teillaud
Administrator
----- Le 25 Juin 19, à 11:55, Stefan Witzel [hidden email] a écrit :

> Hi again,
>
> I am working with a Hyperbolic Delaunay triangulation, more specifically with a
>
> CGAL::Hyperbolic_Delaunay_triangulation_2<CGAL::Hyperbolic_Delaunay_triangulation_traits_2<>>
> dt
>
> Now I'm experiencing the following behavior: I have a program (and a
> set of input) that finishes "immediately" but if I add some code, it
> takes on the order of minutes and more *even in the old part of the
> code*. So clearly there is some side effect, and I'm pretty certain
> that I'm not producing it (the only thing I'm passing around is
> const). For all I can tell the output (of the old part of the code) is
> exactly the same as before so the side effect is restricted to
> runtime.
> So I'm wondering: is it possible that previous calculations performed
> with dt affect future calculations? I'm imagining something like if
> some calculation needed a certain precision (or number field), the
> consecutive calculations are performed with the same precision even
> though they might not need it.

Hi,

Might be, but honestly without a crystal ball that would tell me what yo are doing, I cannot say more...

> If this is the case, is there a way to "reset" the precision?

I don't know much about Core number types, probably the Core manual says something, see https://cs.nyu.edu/exact/core_pages/intro.html (however be aware that the version that we maintain in CGAL is not the same as the native Core)

> P.S.: In case someone has read the previous posts and is wondering: at
> the moment I can't get the circular kernel to work because I don't
> know how to turn a Hyperbolic_Voronoi_point_2 into a
> Hyperbolic_point_2.

I would recommend to have a quick look at the paper that we cite in the Design and Implementation History section: Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry, 5:56–85, 2014. http://hal.inria.fr/hal-00961390.

More details:
Hyperbolic_Voronoi_point_2 is the intersection of two circular arcs whose centers are two Hyperbolic_point_2. So, the coordinates of a Hyperbolic_Voronoi_point_2 lie in an extension field of degree 2, compared to the coordinates of a Hyperbolic_point_2. That's precisely why we have two types in CGAL.
So, if you are using rational input points with CGAL::Hyperbolic_Delaunay_triangulation_CK_traits_2, you cannot convert Hyperbolic_Voronoi_point_2 into Hyperbolic_point_2.
If you are using input points with algebraic coordinates and CGAL::Hyperbolic_Delaunay_triangulation_traits_2, I guess that the two point types are the same (to be checked in the code, they are probably both Point_2<CORE::Expr>).

As mentioned in the manual, if you are just computing hyperbolic Delaunay triangulations and Voronoi diagrams of point sites having rational coordinates, then CGAL::Hyperbolic_Delaunay_triangulation_CK_traits_2 is enough for you. If you are doing something that requires more tricky computations on algebraic numbers, then you need the traits that you are currently using.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Side effects

Stefan Schirra
Hi Monique and Stefan,

not sure whether my 2 cents might be helpful, but may be, they are.

I conclude from Monique's answer that the CGAL code uses CORE::Expr
internally.

>> So I'm wondering: is it possible that previous calculations performed
>> with dt affect future calculations? I'm imagining something like if
>> some calculation needed a certain precision (or number field), the
>> consecutive calculations are performed with the same precision even
>> though they might not need it.

Basically, such expression-dag based number types like CORE::Expr or
leda::real (or Real_algebraic which is still under development) use
adaptive precision computation, i.e., somehow increase the local
precision repeatedly until it suffices. By local I mean the precision
used during a decision making (sign computation). There is no global
overall precision.

There are two strategies when it comes to the next decision making.
Either you keep all the correct information you already have or you
round to a small local starting precision, thereby introducing some
error but making initial computations faster again, and then later
adjust the precision adaptively. To my knowledge, CORE keeps all the
correct information it has in order to avoid redundant recomputation.

>> If this is the case, is there a way to "reset" the precision?

I don't know, but I believe there is nothing like that. Usually, keeping
all the correct information is a fairly good strategy.

>> Now I'm experiencing the following behavior: I have a program (and a
>> set of input) that finishes "immediately" but if I add some code, it
>> takes on the order of minutes and more *even in the old part of the
>> code*.

I do not quite understand what you mean by "add some code", but it is
hard to believe that running time switches form seconds to minutes just
because of keeping correct bits. I guess, there must be other causes,
too, running out of memory for example. But without knowing what you are
actually doing ...

Best regards

        Stefan

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss