Boost logo

Boost :

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:

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at