Rational Arithmetic in C++

Bill Seymour
2023-12-31


Contents


Introduction

This paper describes the public API of an open-source rational number library distributed under the Boost Software License.  (This is not part of Boost.  The author just likes their open-source license.)

A few features:

The rational class is not thread-safe, and a single instance may not appear in multiple threads if it gets modified in any of them.  This includes exposing the value to the outside world which first reduces the fraction to its lowest terms.

The files distributed with the library are:

and you’ll also need the author’s bigint class.

The code can be compiled with any C++ implementation that conforms at least to C++11.

As of this writing, the author is still completing his testing.
Static link libraries with both rational and bigint objects for both Linux and Windows are coming Real Soon Now.


Synopsis

#include "bigint.hpp"

namespace rat {

using dbacc::bigint;

//
// The rational Class
//
class rational final
{
public:
    //
    // Special Member Functions and swap()
    //
    rational();

    ~rational() noexcept;

    rational(const rational&);
    rational(rational&&);

    rational& operator=(const rational&);
    rational& operator=(rational&&);

    void swap(rational&);

    //
    // Construction from Other Types
    // (SFINAE for templates not shown)
    //
    template<typename intT>
    rational(intT);

    template<typename numT, typename denT>
    rational(numT, denT);

    rational(const bigint&);
    rational(bigint&&);
    rational(const bigint&, const bigint&);
    rational(bigint&&, bigint&&);

    template<typename floatT>
    explicit rational(floatT, long double accuracy = 0.0);

    explicit rational(const char*, int radix = 0, const char** = nullptr);
    explicit rational(const std::string&, int radix = 0, std::size_t* = nullptr);

    //
    // Assignment from Other Types
    // (SFINAE for templates not shown)
    //
    template<typename intT>
    rational& operator=(intT);

    template<typename numT, typename denT>
    rational& assign(numT, denT);

    rational& operator=(const bigint&);
    rational& operator=(bigint&&);
    rational& assign(const bigint&, const bigint&);
    rational& assign(bigint&&, bigint&&);

    template<typename floatT>
    rational& assign(floatT, long double accuracy = 0.0);

    rational& assign(const char*, int radix = 0, const char** = nullptr);
    rational& assign(const std::string&, int radix = 0, std::size_t* = nullptr);

    //
    // Observers
    //
    const bigint& numer() const noexcept;
    const bigint& denom() const noexcept;

    bool is_zero() const noexcept;
    bool is_neg()  const noexcept;
    bool is_pos()  const noexcept;
    bool is_one()  const noexcept;
    bool is_one(bool negative) const noexcept;

    bool is_norm() const noexcept;

    explicit operator bool() const noexcept;

    explicit operator long double() const;

    std::string to_string(int radix = 10) const;

    int compare(const rational&) const;

    int signum() const noexcept;

    //
    // Mutators
    //
    rational& set_to_zero();
    rational& set_to_one(bool negative = false);

    rational& negate() noexcept;
    rational& abs() noexcept;

    rational& invert();

    const rational& normalize() const;

    //
    // Arithmetic Operators
    //
    rational& operator++();
    rational& operator--();

    rational  operator++(int);
    rational  operator--(int);

    rational& operator+=(const rational&);
    rational& operator-=(const rational&);
    rational& operator*=(const rational&);
    rational& operator/=(const rational&);

    //
    // Heap Usage
    //
    std::size_t size() const noexcept;
    std::size_t capacity() const noexcept;
    void shrink_to_fit();
};

//
// Non-member Functions
//
using std::swap;
void swap(rational&, rational&);

std::string to_string(const rational&, int radix = 10);

rational reciprocal(const rational&);

//
// Comparisons
//
bool operator==(const rational&, const rational&);
bool operator!=(const rational&, const rational&);
bool operator< (const rational&, const rational&);
bool operator> (const rational&, const rational&);
bool operator<=(const rational&, const rational&);
bool operator>=(const rational&, const rational&);

//
// Non-member Arithmetic Operators
//
rational operator+(const rational&);
rational operator-(const rational&);

rational operator+(const rational&, const rational&);
rational operator-(const rational&, const rational&);
rational operator*(const rational&, const rational&);
rational operator/(const rational&, const rational&);

//
// A Few <cmath>-like Functions
//
enum rounding // for rounding rationals to integer values
{
    all_to_neg_inf, all_to_pos_inf,
    all_to_zero, all_away_zero,
    all_to_even, all_to_odd,
    all_fastest, all_smallest,
    all_unspecified,
    tie_to_neg_inf, tie_to_pos_inf,
    tie_to_zero, tie_away_zero,
    tie_to_even, tie_to_odd,
    tie_fastest, tie_smallest,
    tie_unspecified
};
rational abs(const rational&);
rational round(const rational&, rounding = tie_away_zero);
rational ceil(const rational&);
rational floor(const rational&);
rational trunc(const rational&);
rational rint(const rational&);
rational modf(const rational&, rational* int_part = nullptr);
rational fmod(const rational&, const rational&);
rational remainder(const rational&, const rational&, rounding = tie_to_even);
rational sqr(const rational&);
rational pow(const rational&, int);
rational copysign(const rational&, const rational&);
rational fma(const rational&, const rational&, const rational&);

//
// I/O Operators
//
template<typename Ch, typename Tr>
std::basic_istream<Ch,Tr>& operator>>(std::basic_istream<Ch,Tr>&, rational&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& operator<<(std::basic_ostream<Ch,Tr>&, const rational&);

//
//I/O Manipulators
//
template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& showden1(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& noshowden1(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& divalign(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& nodivalign(std::basic_ostream<Ch,Tr>&);

template<typename Ch>
implementation-detail setdiv(Ch);

} // namespace rat


Detailed Descriptions


The rational Class

Since basically every operation on rational numbers requires multiplication behind the scenes, numerators and denominators can get big in a hurry.  To mitigate the overflow problem, the class is implemented internally using
an unbounded integer for the numerator and denominator.

The class provides implicit conversion from all built-in integers and the bigint type used internally; but it provides only explicit conversion between rationals and built-in floating point values since the principal use for rational numbers is doing arithmetic exactly, but floating point types are inexact in general.

Explicit conversion between rationals and strings is also provided.  The strings may contain octal, decimal or hexadecimal representations.

The class has no NaNs or infinities, so rationals are strongly ordered.

Class invariants:  the class will never represent a negative zero, the denominator will always be greater than zero, and if the numerator is zero the denominator is 1.

Construction and assignment will eagerly normalize the fraction such that the numerator and denominator have no common factor other than 1, but at other times the numerator and denominator are allowed to grow without bound.  There’s a normalize() function that users can call if they think it’s time to try to normalize the fraction, but nothing in the library uses it except during construction and assignment or when the value becomes externally visible.

Issues:
  1. Is there some heuristic to suggest that maybe it’s time to call normalize()?  The author isn’t aware of one.

  2. And what about approximating the value to reduce the sizes of the numerator and denominator?  Should that functionality be included?

  3. The author believes that floating point values can always be converted exactly to rational numbers, but he’s not good enough at numerics to prove that the usual continued fractions algorithm will always find the exact value when that’s what the user requests.  At present, the conversion from floating point values to rationals includes a test of whether the value is no longer converging.  Can that be ripped out?


Special Member Functions and swap()

rational();
The default constructor creates a rational with a numerator equal to 0 and a denominator equal to 1.
~rational() noexcept;
The destructor is non-trivial.
rational(const rational&);
rational(rational&&);

rational& operator=(const rational&);
rational& operator=(rational&&);

void swap(rational&);
rationals are freely copyable, moveable and swappable.


Construction from Other Types

template<typename intT>
rational(intT);

template<typename numT, typename denT>
rational(numT, denT);
A rational may be implicitly constructed from a value of any built-in integer type, and it may be constructed from a pair of built-in integers representing the desired numerator and denominator respectively.

These constructors actually use SFINAE to assure that all arguments are built-in integers.  The details aren’t documented here because they would just obscure the high-level purpose of these constructors.  C++ coders who are familiar with type traits templates will likely find the details unsurprising (and probably tedious as well).

rational(const bigint&);
rational(bigint&&);
rational(const bigint&, const bigint&);
rational(bigint&&, bigint&&);
A rational may also be implicitly constructed from a bigint, and it may be constructed from a pair of bigints representing the desired numerator and denominator respectively.
template<typename floatT>
explicit rational(floatT value, long double accuracy = 0.0);
A rational may be explicitly constructed from a value of built-in floating point type.  (Implicit construction is not allowed because the whole point of doing rational arithmetic is to do it exactly, and floating point types are inexact in general.)  As with the constructors that take built-in integers, SFINAE assures that floatT will be float, double or long double.

The optional second argument can be used to control how accurate the conversion is.  For example, if ±0.1% of value is good enough, you can explicitly pass 0.001.  If you explicitly pass zero, or if you let the argument default to that, the conversion will be exact (in which case you’ll likely get very large numerators and denominators, and the author’s implementation takes almost 6µs to convert DBL_MAX to rational).

This constructor will throw an invalid_argument exception if value is a floating point NaN or infinity.

As currently written, it can also throw a logic_error if it can’t exit its continued fractions loop because the value is no longer converging.  The author doesn’t believe that that can actually happen even if zero is passed as the second argument:  value is a floating point number, not a real number, and so an exact rational equivalent exists; but he’s not good enough at numerics to prove that the continued fractions algorithm can find the value in all cases, so the code to check for that is there just in case.

explicit rational(const char* value, int radix = 0, const char** termchr = nullptr);
explicit rational(const std::string& value, int radix = 0, std::size_t* termpos = nullptr);
A rational may also be explicitly constructed from a string.  The first of these two functions will throw an invalid_argument if value is nullptr, and either will throw an invalid_argument if the string is not in one of the recognized forms, if the string contains no digit at all, or if the denominator is zero.

The string may optionally begin with a '+' or a '-' followed by one of:

If the string contains a '.', it will be taken to be a single number in either fixed point or scientific notation, but hexadecimal strings are not allowed in scientific notation (because an 'E' or 'e' would just be a digit, never the beginning of an exponent).  There must be at least one digit either before or after the '.'.

At present, the functions recognize commas as thousands separators for users who think that that would make their code more readable, but any ',' will just be ignored.  There’s no requirement that they be in the right places.

Octal, decimal and hexadecimal strings are supported.  Hexadecimal digits may be any combination of upper or lower case.

If radix is not one of 8, 10 or 16 (and note that it defaults to 0):

If the function encounters any character that’s not a proper digit for the selected radix (except for the optional sign, base, comma, slash or period), it will just terminate the parse; and so the number may be part of a larger string as long as the number begins the string.

The optional third argument may be used to discover the character that terminated the parse:


Assignment from Other Types

template<typename intT>
rational& operator=(intT);

template<typename numT, typename denT>
rational& assign(numT, denT);

rational& operator=(const bigint&);
rational& operator=(bigint&&);
rational& assign(const bigint&, const bigint&);
rational& assign(bigint&&, bigint&&);

template<typename floatT>
rational& assign(floatT, long double = 0.0);

rational& assign(const char*, int = 0, const char** = nullptr);
rational& assign(const std::string&, int = 0, std::size_t* = nullptr);
All assignment functions have the same semantics as do their corresponding constructors (including SFINAE, not shown, for the three templates).  All return *this.


Observers

const bigint& numer() const noexcept;
const bigint& denom() const noexcept;
These functions return the (possibly unnormalized) numerator and denominator respectively.
bool is_zero() const noexcept;
bool is_neg()  const noexcept;
bool is_pos()  const noexcept;
is_zero() returns whether *this == 0.
is_neg() returns whether *this < 0.
is_pos() returns whether *this > 0.
These are more efficient than comparing *this to the integer 0.
bool is_one() const noexcept;
bool is_one(bool negative) const noexcept;
is_one() with no argument returns whether *this is ±1.
is_one(false) returns whether *this is +1.
is_one(true) returns whether *this is −1.
These are more efficient than comparing *this to the integer 1.
bool is_norm() const noexcept;
This function returns true if it’s known that the numerator and denominator have no common factor other than 1.  If it returns false, that state is unknown.
explicit operator bool() const noexcept;
This is intended to support the “if (my_rat)” idiom.  It returns !this->is_zero().
explicit operator long double() const;
This calls normalize() to lessen the chance of overflow and returns long double(numer()) / long double(denom()).

If either the numerator or the denominator overflows a long double, this function will normally throw an overflow_error; but see the caveats with a yellow background in the bigint documentation.  (It’s the bigint class that actually throws the exception.)

std::string to_string(int radix = 10) const;
This function calls normalize() and then returns a string, possibly beginning with '-' (but never '+'), followed immediately by the numerator, followed immediately by '/', followed immediately by the denominator.  The numerator and denominator will be written as appropriate for the requested radix.  Only octal, decimal and hexadecimal representations are supported; and if radix is not one of 8, 10 or 16, it will default to 10.  Hexadecimal digits will be upper case.  There will be no leading '0' or "0X" to indicate the radix.  If you want something fancier, you can write to a std::basic_ostringstream<>.
int compare(const rational& rhs) const;
This function returns a value less than zero if *this < rhs, zero if *this == rhs, or a value greater than zero if *this > rhs.
int signum() const noexcept;
This function returns −1 if this->is_neg(), 0 if this->is_zero(), or +1 if this->is_pos().


Mutators

rational& set_to_zero();
rational& set_to_one(bool negative = false);
set_to_zero() assigns 0 to *this.
set_to_one(false) assigns +1 to *this.
set_to_one(true) assigns −1 to *this.
These are more efficient than the assignment operator.
rational& negate() noexcept;
This function changes the sign of *this if !this->is_zero().  It will never create a negative zero.
This is more efficient than the non-member unary operator.
rational& abs() noexcept;
This function sets *this to its absolute value.
rational& invert();
This function throws a domain_error exception if the numerator is zero; otherwise it swaps the numerator and denominator, possibly changing the sign of both to guarantee a denominator greater than zero.
const rational& normalize() const;
This function normalizes the fraction such that the numerator and denominator have no common factor other than 1.

Tricky code:  normalize() is declared to be a const member function because the numerical value of the object doesn’t change, although it does change the internal representation, and so the values returned by numer(), denom() and is_norm() could change.  *this is returned by const reference so that we can’t unintentionally play any other tricks later.

The library doesn’t make use of this except during construction and assignment from other types or when the value becomes externally visible, and so the numerator and denominator are normally allowed to grow without bound; but users can call this function if they think that memory usage is getting out of hand (for example, after doing lots of arithmetic which almost certainly requires multiplication behind the scenes).

All of these functions return *this.


Arithmetic Operators

These are all expected to be unsurprising.
rational& operator++();
rational& operator--();

rational  operator++(int);
rational  operator--(int);

rational& operator+=(const rational&);
rational& operator-=(const rational&);
rational& operator*=(const rational&);
rational& operator/=(const rational&);


Heap Usage

These functions relate to the amount of memory allocated on the free store (a.k.a., “heap”) for the numerator and denominator.

The bigint class used for the numerator and denominator is implemented in terms of a std::vector<some built-in unsigned integer type>.  The element type can vary depending on the C++ implementation that you’ve used to compile the code.  

std::size_t size() const noexcept;
std::size_t capacity() const noexcept;
These functions return the total number of bytes used for the numerator and denominator.

If you’d like more detailed information about heap usage, you can call any of numer().size(), numer().capacity(), denom().size() or denom().capacity().  Those bigint member functions have the same semantics as do vector’s functions of the same names, except that the returned values are numbers of bytes, not numbers of container elements (because we’re not sure what the element type is).

void shrink_to_fit();
This function just calls shrink_to_fit() on both the numerator and the denominator.


Non-member Functions

using std::swap;
void swap(rational& lhs, rational& rhs);
As if:  lhs.swap(rhs);
std::string to_string(const rational& val, int radix = 10);
As if:  return val.to_string(radix);
rational reciprocal(const rational& val);
As if:  return rational(val).invert();


Comparisons

bool operator==(const rational&, const rational&);
bool operator!=(const rational&, const rational&);
bool operator< (const rational&, const rational&);
bool operator> (const rational&, const rational&);
bool operator<=(const rational&, const rational&);
bool operator>=(const rational&, const rational&);
Since rationals have no NaN or infinity values, they’re strongly ordered.


Non-member Arithmetic Operators

These are all expected to be unsurprising.
rational operator+(const rational&);
rational operator-(const rational&);

rational operator+(const rational&, const rational&);
rational operator-(const rational&, const rational&);
rational operator*(const rational&, const rational&);
rational operator/(const rational&, const rational&);


A Few <cmath>-like Functions

The library supplies several <cmath>-like functions that can be expected to return exact values.  All are intended to mimic the standard library functions of the same name.

Also supplied are rounding modes for use when rounding rationals to integers.

enum rounding
{
    all_to_neg_inf, all_to_pos_inf,
    all_to_zero, all_away_zero,
    all_to_even, all_to_odd,
    all_fastest, all_smallest,
    all_unspecified,
    tie_to_neg_inf, tie_to_pos_inf,
    tie_to_zero, tie_away_zero,
    tie_to_even, tie_to_odd,
    tie_fastest, tie_smallest,
    tie_unspecified
};
The rounding modes are borrowed from WG21’s P1889R1 §3.3.  Note that it’s an unscoped enumeration, so the enumerators are in the rat namespace.  All of the …fastest, …smallest and …unspecified modes behave like their corresponding …to_zero modes.
rational abs(const rational&);
rational round(const rational&, rounding = tie_away_zero);
rational ceil(const rational&);
rational floor(const rational&);
rational trunc(const rational&);
rational rint(const rational&);
rational modf(const rational&, rational* int_part = nullptr);
rational fmod(const rational&, const rational&);
rational remainder(const rational&, const rational&, rounding = tie_to_even);
rational sqr(const rational&);
rational pow(const rational&, int);
rational copysign(const rational&, const rational&);
rational fma(const rational&, const rational&, const rational&);
Note that a rounding mode may be passed to rat::round().  The default, tie_away_zero, mimics std::round().

Similarly, a rounding mode may be passed to rat::remainder().  The default, tie_to_even, mimics std::remainder().

The second argument to modf() can be nullptr, and defaults to nullptr, in which case the function will just return the fractional part of the value.

Note that the exponent to rat::pow() must be an integer since raising to a non-integer power yields an irrational value in general.

rat::fma() doesn’t do anything special since no rounding would occur between the multiplication and the addition in any event; but it’s included because it’s canonical, and it could help with converting existing code to use rationals instead of floating point types.  The standard FP_FAST_FMA macro tells you nothing about this function.


Formatted I/O

The library provides the canonical iostream insertion and extraction operators.  They’re localized (ctype and numpunct facets) and recognize all the ios_base and basic_ios<> formatting facilities that make sense for integers (because the numerator and denominator are integers).  There are also five I/O manipulators described below that apply to rationals.

The division sign will be whatever character, narrow or wide, has been set by the setdiv() manipulator below.  The default is stream.widen('/').


I/O Operators

template<typename Ch, typename Tr>
std::basic_istream<Ch,Tr>& operator>>(std::basic_istream<Ch,Tr>&, rational&);
Leading whitespace will be ignored if skipws is in effect, then the input may be either a single integer (which will be the numerator and the denominator will be one), or two integers separated by a division sign (in which case the first will be the numerator and the second the denominator).

A denominator may optionally begin with a '+' or '-'.  H. sapiens would probably never write that, but it’s not hard to imagine machine-generated strings coming out that way.  In any event, assigning the value to the right-hand operand will enforce the class invariant that the denominator always be greater than zero.

If the operator reads a value of zero when expecting a denominator, it will set the stream’s failbit which could throw an ios_base::failure if the user has set up the stream to do so.  If the exception is thrown, or if the stream is not good() when the operator returns, the operator might have removed a number of characters from the stream; but the rational on the right-hand side will be untouched.

The stream’s locale and all its format flags except skipws apply separately to the numerator and the denominator.  skipws applies to the numerator only; so there may be no whitespace between the numerator, the division sign, and the denominator.

The oct, dec and hex flags are the only way to select the radix.  There’s no way to override them by including an indication of the base in the string.  (Hexadecimal input may begin with "0X" or "0x", but it will just be ignored.)

At present, the operator recognizes localized thousands separators but just ignores them.  It doesn’t require that they be in the right places.

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& operator<<(std::basic_ostream<Ch,Tr>&, const rational&);
The insertion operator normalizes its right-hand operand and writes a rational to the specified output stream, the numerator and denominator being written in whatever format is appropriate given the stream’s flags and locale.  The showpos and showbase flags affect the numerator only.

The output will be an optional sign or base, followed by the numerator, followed (usually immediately) by a division sign, followed immediately by the denominator.  If the denominator is 1, output of the division sign and the '1' can be suppressed with the noshowden1 manipulator described below (and noshowden1 is the default).


I/O Manipulators

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& showden1(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& noshowden1(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& divalign(std::basic_ostream<Ch,Tr>&);

template<typename Ch, typename Tr>
std::basic_ostream<Ch,Tr>& nodivalign(std::basic_ostream<Ch,Tr>&);

Two new pairs of no-argument output manipulators provide additional formatting options when writing rationals.

showden1 and noshowden1 control whether a denominator equal to 1 is written.  If noshowden1 is in effect and the denominator is 1, neither the division sign nor the '1' will be written; so the output will be just the numerator written as an ordinary integer.

divalign and nodivalign control whether the stream’s width and adjustfield flags affect the numerator only (divalign) or the whole fraction (nodivalign).  The former is intended for printing fractions in columns by lining up the division signs.

The defaults are noshowden1 and nodivalign.

For example:

    rational r1(5);
    rational r2(24, 17);
    cout << r1 << '\n'
         << r2 << '\n'
         << showden1
         << setfill('*')
         << setw(6) << r1 << '\n'
         << setw(6) << r2 << '\n'
         << divalign
         << setw(6) << r1 << '\n'
         << setw(6) << r2 << '\n'
         << left << setfill(' ') << setw(6) << r2
         << " (You might want to avoid left with divalign.)\n";
yields the output:
    5
    24/17
    ***5/1
    *24/17
    *****5/1
    ****24/17
    24    /17 (You might want to avoid left with divalign.)

template<typename Ch> implementation-detail setdiv(Ch);
This one-argument I/O manipulator sets the character to be used for the division sign.  For example:
    cout << setdiv('÷') << rational(1,3);
yields the output:
    1÷3
As expected, the default division sign is stream.widen('/').

All these manipulators call ios_base::iword() and have no additional effect if that function fails and sets the stream’s badbit.

Note that the compiler can’t find any of these manipulators by argument-dependent lookup (ADL); so you’ll need to either explicitly qualify their use with the rat namespace or have a using declaration for them.


If You Don’t Need I/O

Although it’s not shown above, if you won’t be doing any I/O of rationals in a particular translation unit (TU), you can #define RATIONAL_NO_IO_OPERATORS before you include rational.hpp, which might save compilation time in complicated builds, although it won’t reduce code size or running time.  You can define that macro in some TUs and not in others without fear of violating the one definition rule (ODR).

The actual code in rational.hpp is:
  } // end of namespace rat
  #ifndef RATIONAL_NO_IO_OPERATORS
    #include "rational_io.hpp"
  #endif
and rational_io.hpp contains the actual template definitions in the rat namespace.  The hope is that the compiler’s lexer won’t even have to scan that code if it doesn’t need to.

rational_io.hpp is a proper header file beginning and ending in the global namespace, and with the usual include guard.  If you include rational.hpp with RATIONAL_NO_IO_OPERATORS defined, you can still get the I/O operators later in the same TU by explicitly including rational_io.hpp yourself.  It’s not clear why you’d want to do that, but there it is.
And note that any explicit #include of rational_io.hpp may appear only in the global namespace for ADL to find the operators.


All suggestions and corrections will be welcome; all flames will be amusing.
Mail to was@pobox.com