[boost] lazy exact arithmetic

From: Brandon Kohn (bkohn_at_[hidden])
Date: 2005-02-19 05:15:26

Hello,

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 
compare.

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?

Kind regards,
Brandon