c++boost.gif (8819 bytes) Rational Numbers

Rationale

Numbers come in many different forms. The most basic forms are natural numbers (non-negative "whole" numbers), integers and real numbers. These types are approximated by the C++ built-in types unsigned int, int, and float (and their various equivalents in different sizes).

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.

Background

The mathematical concept of a rational number is what is commonly thought of as a fraction - that is, a number which can be represented as the ratio of two integers. This concept is distinct from that of a real number, which can take on many more values (for example, the square root of 2, which cannot be represented as a fraction).

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.

Integer Type Requirements

The rational type takes a single template type parameter I, which must be a model of the following concepts.

Furthermore, I must be an integer-like type, that is the following expressions must be valid for any two values n and m of type I, with the "expected" semantics. In particular, division should truncate.

It is valid for I to be an unsigned type. In that case, the derived rational class will also be unsigned. Underflow behaviour of subtraction, where results would otherwise be negative, is unpredictable in this case.

Interface

Two utility functions are provided, which work on any types for which the following operations are defined: =, +=, *=, /=, %, <

gcd(n, m) The greatest common divisor of n and m
lcm(n, m) The least common multiple of n and m

All of the standard numeric operators are defined for the rational class. These include:

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

Furthermore, input and output operators << and >> are provided. The external representation of a rational is two integers, separated by a slash (/). On input, there must be no space between the numerator and the slash.

Rationals can be constructed from a pair (numerator, denominator) of integers, or a single integer. There is also a default constructor, which initialises the rational to a value of zero.

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

For any rational<I> r, r.assign(n, m) provides a fast equivalent of r = rational<I>(n, m);, without the construction of a temporary. While this is probably unnecessary for rationals based on machine integer types, it could offer a saving for rationals based on unlimited-precision integers, for example.

There are no implicit conversions from rationals to any other type. However, there is an explicit type-conversion function, rational_cast<T>(r). This can be used as follows:

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

Finally, access to the internal representation of rationals is provided by the two member functions numerator() and denominator().

Exceptions

Rationals can never have a denominator of zero. (This library does not support representations for infinity or NaN). Should a rational result ever generate a denominator of zero, the exception boost::bad_rational (a subclass of std::domain_error) is thrown.

Internal representation

Note: This information is for information only, and should be assumed to be subject to change without notice. Should the internal representation change, it is possible that the semantics of the numerator() and denominator() functions will change as well. Use at your own risk.

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 normalised form (ie, gcd(numerator,denominator) = 1, and the denominator is always positive).

Note that the range of values representable in a rational is dependent upon the denominator. If the denominator is 1, the range is the same as that of the underlying integer type. If the denominator is equal to the maximum representable value in the underlying integer type, the maximum value is (approximately) 1.

References

History and Acknowledgements

In December, 1999, I implemented the initial version of the rational number class, and submitted it to the boost mailing list. Some discussion of the implementation took place on the boost.org mailing list. In particular, Andrew D. Jewell pointed out the importance of ensuring that the risk of overflow was minimised, and provided overflow-free implementations of most of the basic operations. The name rational_cast was suggested by Kevlin Henney. Ed Brey provided invaluable comments - not least in pointing out some fairly stupid typing errors in the original code!

Revised  December 14, 1999

© Copyright Paul Moore 1999. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.