Re: [boost] Rational precision issues (Was: Standardization of Boost libraries)

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-03-12 08:04:31

----- Original Message -----
From: "Moore, Paul" <paul.moore_at_[hidden]>
To: <boost_at_[hidden]>
Cc: "Chuck Allison" <cda_at_[hidden]>
Sent: Tuesday, March 12, 2002 5:54 AM
Subject: [boost] Rational precision issues (Was: Standardization of Boost
libraries)

> [SNIPPED]
>
> I have yet to get a good feel for whether "real world" use of rationals
> would hit problems with 32-bit integer precision. My view is that *if* it
> isn't a practical problem, then simply documenting the issue (as I have
> tried to do in the rational.hpp documentation) is enough. If these
problems
> do hit real-world applications, though, it may be better not to have a
> templated rational class at all, and force use of unlimited-precision
> integers as part of the class implementation...
>
> I have a sneaking suspicion that no-one *really* knows if this would be an
> issue in practice :-(
>
I known that you normally cannot use fixed-precision rational arithmetic in
computational geometry, not only because of possible overflow but because
the reason to use rational arithmetic in CG is to get *exact* results for
affine point arithmetic.  In this scenario, you need to use all the required
extra bit complexity (that is, normalization is required not to round).
Rational addition, for instance, can *double* bit complexity in order to
achieve an exact result.
Also, if the endpoints of two line segments are given with rational
coordinates, the coordinates of their intersection point requires a bit
complexity which can bubble in a factor of 8 in order to be exact.

Anyway, in spite of the fact that rational<fixed-size-int> cannot be made
exact w.r.t affine arithmetic, as it could if used with an unlimited size
integer, I once tried boost::rational<int> as the coordinate
rerepresentation for my systems. It didn't worked. Overflow appeared to
soon!
Even worst, since in a Win32 machines integer overflow doesn't raise any
exceptions (at least not in the way Borland compiles it), you don't get an
error what just a plain wrong result really really really hard to trace
down.
(This was the factual case even though boost::rational<> is very careful
with respect to overflow)

I think that a potential problem with a 'bare' integral type as the *only*
rational 'policy' is that overflow cannot be detected so it goes unnoticed.
In my case, unfortunately, this rendered boost::rational totally unusable.
Each and every other rational number class that I use, either use only
arbitrary/adaptive precision integers (so overflow never occurs), or are
black-boxes which handle overflow conditions by themselves.

I know that rational itself would behave appropriately if the appropriate
integer types are used, but it will fail miserably if built-in integers are
used and overflow arises (which at least in my case does).

A possible solution -off the top of my head- is to use some variation of a
trick I use in my systems:

class rational<class IntType, class ArithmeticKernel>
{
  some_fun()
  {
     IntType a = ArithmeticKernel::add(b,c) // instead of "b + c"
  }
}

The trick is conceptually simple: rational<> doesn't use operators directly
but functions which are supplied by the user and which 'somehow' are
supposed to deal with overflow (by throwing an exception or by avoiding it).

For example, using something like this:

template<class U>
struct def_arithmetic_kernel
{
  template<class T>
  T add ( T x, T y )
  {
     U x_ = numeric_cast<U>(x) ;
     U y_ = numeric_cast<U>(y) ;
     U r = x_ + y _ ;
     return numeric_cast<T>(r);
  } ;

and

typedef rational<int, def_arithmetic_kernel<long long> > rat ;

can at least reduce the chances of overflow because 'int' values are
converted to 'long long', operated, and then rounded back to 'int'.

Anyway, this is just a naive example to show that an additional 'arithmetic
policy can be used to deal with overflow externally (it can even be
reusable), and, IMO is a requirement for rational<>.

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com