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
"Brandon Kohn" <bkohn@monaco377.com> writes:
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 don't think I can devote any time to the actual development, but I'm very interested in the outcome.
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.
Great; are you aware of http://www.boost.org/libs/numeric/interval/doc/interval.htm ?? Could you use that as a substrate? -- Dave Abrahams Boost Consulting www.boost-consulting.com
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 +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com | -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Brandon Kohn | Sent: 19 February 2005 10:15 | To: boost@lists.boost.org | 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 | |
I'm glad there is some interest. I've already begun implementing it (will be testing it with GMP). I noticed (I think 3) implementations of big_integer classes in the yahoo group files section. None of them has ripened into a solid library so far? Or are they just not entirely compatible with boost::rational? Boost seems fairly ready for this stage of evolution what with interval and rational... so perhaps it's just a matter of time for big_int to be completed. At any rate, I'll continue my work and post more when I have something worth reporting (or ?s). Thanks guys, Brandon "Paul A Bristow" <pbristow@hetp.u-net.com> wrote in message news:E1D3bdc-0007Gk-SA@he303war.uk.vianw.net...
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 +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Brandon Kohn | Sent: 19 February 2005 10:15 | To: boost@lists.boost.org | 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 | |
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
At 03:04 PM 2/22/2005, Brandon Kohn wrote:
I'm glad there is some interest. I've already begun implementing it (will be
testing it with GMP). I noticed (I think 3) implementations of big_integer classes in the yahoo group files section. None of them has ripened into a
solid library so far? Or are they just not entirely compatible with boost::rational?
My guess is that no one wanted to put the time in to polish their preliminary efforts enough to get ready for a review. By the way, Michiel Salters has proposed a big integer class for the next C++ standard library technical report. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1744.pdf It isn't clear to me if his proposal represents actual existing practice, or is just a strawman proposal. --Beman
Hello again, I've got a first draft of the lazy exact arithmetic library put together. I've done all my preliminary testing using the gmp rational type. Strangely enough, when I tried using the boost rational type with the gmp arbitrary integer type, many of the results for calculations such as pi or Newton's square root were churning out undefined doubles. They seemed to work under the gmp rational. (Not sure why... perhaps something to do with the way I was initializing rational from double). I am putting this version out with a 'release early, release often' strategy in the hopes that the community dev-machine will help me move it forward. I've put a file up on the yahoo groups file section at : http://f2.grp.yahoofs.com/v1/QLYhQlr5V5P4sV_haWfJIVsKZ8_lrbE5Z9BsvsKZvT-p0sg... I've got testbeds built on visual studio .NET 2003 if anyone is interested in a having a look.. just contact me. Otherwise, if you would.. have a look and help me kick this thing around. :) Best, Brandon "Brandon Kohn" <bkohn@monaco377.com> wrote in message news:cv73e5$7hv$1@sea.gmane.org...
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
On Sun, 27 Feb 2005 14:02:36 +0100, Brandon Kohn wrote
I've put a file up on the yahoo groups file section at :
This link didn't work for me. Might I suggest you put your files in the new 'Sandbox vault' instead. We are trying to move away from Yahoo Groups so people don't have to a have a login to download new libs. You'll need to register to upload, though. http://boost-sandbox.sourceforge.net/vault/ Jeff
participants (5)
-
Beman Dawes -
Brandon Kohn -
David Abrahams -
Jeff Garland -
Paul A Bristow