RE: [boost] lazy exact arithmetic

From: Paul A Bristow (pbristow_at_[hidden])
Date: 2005-02-22 10:07:46

This looks very useful - if a minority pastime,
but since Boost has yet to get a yet-to-be Boost big_integer to work with
Boost rational,
it might be running before walking.

However, exposing your impressive work to Boosters view must be good.

Paul

Paul A Bristow
Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB
[phone]  [phone]
mailto: pbristow_at_[hidden]

| -----Original Message-----
| From: boost-bounces_at_[hidden] 
| [mailto:boost-bounces_at_[hidden]] On Behalf Of Brandon Kohn
| Sent: 19 February 2005 10:15
| To: boost_at_[hidden]
| Subject: [boost] lazy exact arithmetic
| 
| 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 
| 
| 
| 
| _______________________________________________
| Unsubscribe & other changes: 
| http://lists.boost.org/mailman/listinfo.cgi/boost
| 
|