[geos-devel] QD (Quad-Double) Approach to Robustness

strk at refractions.net strk at refractions.net
Wed Jun 14 13:44:59 EDT 2006


Sounds interesting, I might make some experimentations with it.

Anyway, I dunno if this could fix the FP problems I reported
here:
http://geos.refractions.net/pipermail/geos-devel/2006-April/002185.html

I've been the whole day tracking a problem that turned out
to be a consequence of that madness. The attached XML testcase
fails with the "inlined" GEOS version but succeeds with 
the "outlined" version (./configure --disable-inline).
I found out that either always outlining Coordinate copy
ctor and assignment operator OR letting the compiler syntetize
them makes both versions succeed.
Logs showed subtle differences in Coordinate double values.
These differences triggered a different result from EdgeEnd::compareTo
that in turn triggered a different order in the EdgeEndStar components
(theoretically to be ordered CCW around the x axis).

The moral of the story is that we really need a way to make
fp operations predictable, or each run will depend on voodoo
parameters.

The QD library provides 'fpu_fix_start' and 'fpu_fix_end'
functions that seems to address this specific problem.
I will give them a try and let you know.
If you have suggestions to model generic library startup
code in C++ I'd appreciate it (a static Init class?)

--strk;


On Mon, Jun 12, 2006 at 03:11:01PM -0700, Paul Ramsey wrote:
> In a conversation with Dale Lutz at GeoAlberta, he mentioned they had  
> experimented with using the QD library (<http://crd.lbl.gov/~dhbailey/ 
> mpdist/>) in some of their topology processing and found that it was  
> exceptionally good at bypassing problems caused by reduced  
> precision.  Presumably this is because all the input data is at  
> double precision, at most, so relative to the processing precision  
> (quad) it is quite well behaved.  The approach was so good that in a  
> race between the old algorithms (double precision but with lots of  
> tests and bobbing and weaving to catch special cases) and the new  
> (quad precision, with no special cases at all, just naive algorithms)  
> the qd won hands down.  So the overhead of the math library on all  
> cases was not higher than the overhead of finding and handling the  
> special cases.
> 
> Something to look at!
> 
> P
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel

-- 

 /"\    ASCII Ribbon Campaign
 \ /    Respect for low technology.
  X     Keep e-mail messages readable by any computer system.
 / \    Keep it ASCII. 




More information about the geos-devel mailing list