Rational precision issues (Was: Standardization of Boost librarie s)

From: Moore, Paul (paul.moore_at_[hidden])
Date: 2002-03-12 03:54:12

From: "Chuck Allison" <cda_at_[hidden]>
> Please pardon my naievete, but isn't the underlying numeric 
> type to rational a template parameter (I don't have the
> class handy)? Isn't it equipped therefore to use an
> instantiation based on unlimited precision integers? If
> not, could you please explain why not. (I assume that an 
> unlimited precision integer package would overload
> the pertinent operators).

The rational<> class will work fine with an unlimited-precision type. The
problem arises when the rational<> type is used with a *limited* precision
integer type. Here, overflow issues raise their ugly heads.

Imagine, for example, a single-digit decimal type I. Now consider
rational<I>.

rational<I> r1(1,4); // No problem - one quarter
rational<I> r2(1,3); // Again, no problem, one third

// Now watch: The correct answer is seven twelfths. But the
// denominator (12) is not representable as a value of type I!
// We can't rely on overflow like this raising an exception,
// as the built-in int type doesn't. So what do we do? Silently
// give the wrong answer? Try to detect overflow manually, which
// is expensive, hurting "normal" performance for the benefit of
// an extreme case?
rational<I> r3 = r1 + r2;

Worse still is the fact that for "real" 32-bit integers, this problem isn't
going to hit often, making it even nastier (due to unexpectedness) when it
does. And there are (potentially) worse cases, where the result is in the
representable range, but intermediate results overflow, unless you take
extreme measures to avoid it (and I'm not sure it's theoretically possible
to avoid intermediate overflow in all cases). As a (trivial) example here,
try 1/6 + 1/2. The result is 4/6, but the naive algorithm works via
twelfths.

These sorts of problems plague floating point arithmetic. People are likely
to use rationals as a way of avoiding the problems perceived with floating
point. If rationals merely exchange a set of commonly known problems for a
set of equally subtle but less well-known problems, they haven't actually
helped!!

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 :-(

Paul.