[boost] Re: lazy exact arithmetic

From: Brandon Kohn (bkohn_at_[hidden])
Date: 2005-02-27 08:02:36

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-p0sgTp6evFo5-ePQXITZJ8qhbcr2Zi0NTwYMw5TEfOqnF_CI2/lazy_exact_arithmetic_0_1.zip

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_at_[hidden]> wrote in message 
news:cv73e5$7hv$1_at_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
>