Rational Numbers

The C++ Standard Library extends the range of numeric types available by providing the complex type.

This library provides a further numeric type, the rational numbers.

The rational class is actually a implemented as a template, in a similar manner to the standard complex class.

Computers cannot represent mathematical concepts exactly - there are always compromises to be made. Machine integers have a limited range of values (often 32 bits), and machine approximations to reals are limited in precision. The compromises have differing motivations - machine integers allow exact calculation, but with a limited range, whereas machine reals allow a much greater range, but at the expense of exactness.

The rational number class provides an alternative compromise. Calculations with rationals are exact, but there are limitations on the available range. To be precise, rational numbers are exact as long as the numerator and denominator (which are always held in normalized form, with no common factors) are within the range of the underlying integer type. When values go outside these bounds, overflow occurs and the results are undefined.

The rational number class is a template to allow the programmer to control the overflow behaviour somewhat. If an unlimited precision integer type is available, rational numbers based on it will never overflow and will provide exact calculations in all circumstances.

Note: In the future, these functions may be moved into a separate boost utility library.

This implies that the following statements are valid:

    I n, d;
    rational<I> zero;
    rational<I> r1(n);
    rational<I> r2(n, d);

The single-argument constructor is not declared as explicit, so there is an implicit conversion from the underlying integer type to the rational type.

    +    +=
    -    -=
    *    *=
    /    /=
    ++   --    (both prefix and postfix)
    ==   !=
    <    >
    <=   >=

    rational r(22,7);
    double nearly_pi = boost::rational_cast<double>(r);

Implementation note:

The actual implementation of the rational_cast function is

    template <typename Float, typename Int>
    Float rational_cast(const rational<Int>& src)
    {
        return static_cast<Float>(src.numerator()) / src.denominator();
    }

These functions allow user code to implement any additional required functionality. In particular, it should be noted that there may be cases where the above rational_cast operation is inappropriate - particularly in cases where the rational type is based on an unlimited-precision integer type. In this case, a specially-written user-defined conversion to floating point will be more appropriate.

In addition, if operations on the underlying integer type can generate exceptions, these will be propogated out of the operations on the rational class. No particular assumptions should be made - it is only safe to assume that any exceptions which can be thrown by the integer class could be thrown by any rational operation. In particular, the rational constructor may throw exceptions from the underlying integer type as a result of the normalization step. The only exception to this rule is that the rational destructor will only throw exceptions which can be thrown by the destructor of the underlying integer type (usually none).

Internally, rational numbers are stored as a pair (numerator, denominator) of integers (whose type is specified as the template parameter for the rational type). Rationals are always stored in fully normalized form (ie, gcd(numerator,denominator) = 1, and the denominator is always positive).

Areas where this minimality consideration has been relaxed are in providing input/output operators, and rational_cast. The former is generally uncontroversial. However, there are a number of cases where rational_cast is not the best possible method for converting a rational to a floating point value (notably where user-defined types are involved). In those cases, a user-defined conversion can and should be implemented. There is no need for such an operation to be named rational_cast, and so the rational_cast function does not provide the necessary infrastructure to allow for specialisation/overloading.

Unfortunately, the C++ standard does not offer such a class (and neither does boost, at the present time). It is therefore likely that the rational number class will in many cases be used with limited-precision integer types, such as the built-in int type.

When used with a limited precision integer type, the rational class suffers from many of the precision issues which cause difficulty with floating point types. While it is likely that precision issues will not affect simple uses of the rational class, users should be aware that such issues exist.

As a simple illustration of the issues associated with limited precision integers, consider a case where the C++ int type is a 32-bit signed representation. In this case, the smallest possible positive rational<int> is 1/0x7FFFFFFF. In other words, the "granularity" of the rational<int> representation around zero is approximately 4.66e-10. At the other end of the representable range, the largest representable rational<int> is 0x7FFFFFFF/1, and the next lower representable rational<int> is 0x7FFFFFFE/1. Thus, at this end of the representable range, the granularity ia 1. This type of magnitude-dependent granularity is typical of floating point representations. However, it does not "feel" natural when using a rational number class.

It is up to the user of a rational type based on a limited-precision integer type to be aware of, and code in anticipation of, such issues.

The key issue with any conversion function from a floating point value is how to handle the loss of precision which is involved in floating point operations. To provide a concrete example, consider the following code:

    // These two values could in practice be obtained from user input,
    // or from some form of measuring instrument.
    double x = 1.0;
    double y = 3.0;

    double z = x/y;

    rational<I> r = rational_from_double(z);

The fundamental question is, precisely what rational should r be? A naive answer is that r should be equal to 1/3. However, this ignores a multitude of issues.

In the first instance, z is not exactly 1/3. Because of the limitations of floating point representation, 1/3 is not exactly representable in any of the common representations for the double type. Should r therefore not contain an (exact) representation of the actual value represented by z? But will the user be happy with a value of 33333333333333331/100000000000000000 for r?

Before even considering the above issue, we have to consider the accuracy of the original values, x and y. If they came from an analog measuring instrument, for example, they are not infinitely accurate in any case. In such a case, a rational representation like the above promises far more accuracy than there is any justification for.

All of this implies that we should be looking for some form of "nearest simple fraction". Algorithms to determine this sort of value do exist. However, not all applications want to work like this. In other cases, the whole point of converting to rational is to obtain an exact representation, in order to prevent accuracy loss during a series of calculations. In this case, a completely precise representation is required, regardless of how "unnatural" the fractions look.

With these conflicting requirements, there is clearly no single solution which will satisfy all users. Furthermore, the algorithms involved are relatively complex and specialised, and are best implemented with a good understanding of the application requirements. All of these factors make such a function unsuitable for a general-purpose library such as this.

The first issue is that, in order to locate the appropriate implementation of abs(IntType) in the case where IntType is a user-defined type in a user namespace, Koenig lookup is required. Not all compilers support Koenig lookup for functions at the current time. For such compilers, clumsy workarounds, which require cooperation from the user of the rational class, are required to make things work.

The second, and potentially more serious, issue is that for non-standard built-in integer types (for example, 64-bit integer types such as long long or __int64), there is no guarantee that the vendor has supplied a built in abs() function operating on such types. This is a quality-of-implementation issue, but in practical terms, vendor support for types such as long long is still very patchy.

As a consequence of these issues, it does not seem worth implementing abs(rational<IntType>) in terms of abs(IntType). Instead, a simple implementation with an inline implementation of abs() is used:

    template <typename IntType>
    inline rational<IntType> abs(const rational<IntType>& r)
    {
        if (r.numerator() >= IntType(0))
            return r;

            return rational<IntType>(-r.numerator(), r.denominator());
    }

The same arguments imply that where the absolute value of an IntType is required elsewhere, the calculation is performed inline.