
Boost : 
Subject: Re: [boost] Arbitrary precision arithmetic
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 20090819 03:06:16
Stephen Nuchia wrote:
...
>
> If I grok the proto stuff correctly it should be possible to write
> expressions that can be evaluated in different contexts. One could be
> native hardware FP arithmetic, one could be the reference bignum
> library, and one could even use GMP. Right?
>
> swn
>
FWIW, I've implemented and used an arithmetic expression evaluation
library for use in geometric computations. It uses expression templates
(via Boost.Proto) to construct staticallytyped expression trees, which
can then be evaluated with any userdefined evaluator (e.g., with
Boost.Interval, extended precision floating point type, exact rational
type, etc.). This allows arithmetic expressions to be adaptively
evaluated until a certain geometric test is conclusive.
For example, to determine if 2 segments intersect, one can compute the
relevant signed areas using Boost.Interval, and if rounding errors cause
the test to be inclusive, you can reevaluate with a more precise data
type. Our application currently only involves polytopic primitives
(points, segments, triangles, tetrahedrons), so expressions involving +,
, *, and / are all we need.
There's also a generic expression type that typeerases a
staticallytyped expression (similar to Boost.Function), which doubles
as a cache of evaluation results (the specification of the caching
strategy is, however, somewhat more complicated than I'd like, since one
must specify how a cached value can be converted to the various possible
evaluation types).
FWIW2, to exactly evaluate expressions, we use a C++ implementation of
JR Shewchuk's expansion arithmetic algorithms:
http://www.cs.cmu.edu/~quake/robust.html
The idea is to represent a number as a sum of fixedprecision floating
point numbers (floats or doubles), and operate on these sums. Our
motivation was the ease with which a float or double can be converted to
this representation, and the operations can generally be very fast, but
I regret I haven't done any benchmarks myself to compare the
computational speed of these algorithms to alternatives. It would seem
to me that an expansion arithmetic type would probably only be useful if
you know the depth of the expression trees in your application aren't
too deep, and you're willing to accept the possibility of running out of
exponent space (overflowing or underflowing). It does happen to work
quite well for our computational geometry application.
Just throwing out some ideas and my own experience in this (or a
possibly tangential) area.
 Jeff
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk