On Thu, May 31, 2012 at 5:31 PM, Marc Glisse <marc.glisse@inria.fr> wrote: [...]
On Thu, 31 May 2012, John Maddock wrote:
[...]
* what about infinite precision floats? By that I mean something like
bigint*2^n, where operations + - * are computed exactly. It can be quite a bit faster than rationals, when it is sufficient.
Wouldn't those get horribly large very quickly?
You can see them as a special case of rationals where the denominator is always a power of 2, so they grow more slowly than rationals.
Off hand I know of no other library that implements such a beast?
CGAL. If you want to evaluate exactly the sign of a polynomial of double, your best bets are this or a sum-of-double representation, depending on the degree.
I want to echo Marc's comment that algorithms and numeric types where you only perform ring operations are common in computational geometry. You can often bound the size of your expression tree (as a function of your spatial dimension), hence bound the size of your rationals. It might be worth considering this application within the scope of (proposed) Boost.Multiprecision. Indeed, I've used a C++ implementation of Jonathan Shewchuck's exact arithmetic algorithms [1] for such purposes. [1] http://www.cs.cmu.edu/~quake/robust.html - Jeff