Re: [boost] Arbitrary precision arithmetic

Subject: Re: [boost] Arbitrary precision arithmetic
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 2009-08-19 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 statically-typed expression trees, which 
can then be evaluated with any user-defined 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 type-erases a 
statically-typed 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 fixed-precision 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