From: Brandon Kohn (bkohn_at_[hidden])
Date: 2005-02-19 05:15:26
I was just posting to see if there is any interest in developing a library
to help with exact arithmetic using the lazy arithmetic strategy?
I've been working for the last couple of years with computational geometry
algorithms, and have found that such a library is really essential to
overcoming problems due to floating point precision/round off errors in most
computational geometry algorithms with non-brute force complexity. The idea
behind the lazy paradigm is that exact computation (using rational
arithmetic with arbitrary sized integers) is too costly to be used all the
time. So the exact computations are delayed until such a time as you cannot
reliably make decisions with the information you have from the 'lazy'
filters. The lazy filters are implemented as a layer of calculation that
uses interval arithmetic to compare numerical quantities. If the intervals
being compared are non-overlapping, the result is considered to be
sufficient and exact computation is avoided. If the intervals do overlap,
exact computation is required to unambiguously decide how the quantities
This is just a rough outline of how the method works, and I'm sure there
will be plenty of kinks to work out (my background is in physics and
computer science... so perhaps a mathematician in the group would step up to
help guide my efforts :).
A library such as this one exists in the CGAL kernel library which is
available under the LGPL. I find that while the LGPL can be useful in cases
where the library is already organized as a single DLL/shared object
library, it is generally difficult to implement into commercial solutions
due to the dynamic linking constraints imposed by the library. Further, I
think that this type of algorithm (which solves a very big problem with
floating point arithmetic in computing) is really something that should be
standardized and freely available.
Sorry for the long post :)
What do you guys think?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk