Doc No: N3414 = 12-0104
Date: 2012-09-12
Reply to:  Bill Seymour, <stdbill.h@pobox.com>

A Rational Number Library for C++

Bill Seymour
2012-09-12

Introduction:

 This paper proposes a rational number library for a C++ Technical Specification (TS) (née Type II Technical Report (TR)).

This is a rewrite of N3363. Many thanks to Daniel Krügler for several excellent suggestions.

The main difference between this paper and N3363 is that the internal integer type is now assumed to be a bignum (Pete Becker’s N3417, for example); and there has been little interest in making rational a template, so that will not be proposed.

One goal I have is to make the class usable by novices; and I think that means that I provide I/O and a handful of <cmath>-like functions that make sense for rationals. Daniel Krügler suggested a few others including round, which I’ve added, and scalbn, scalbln and copysign which I haven’t yet. Daniel also questioned the names of the fmod, modf and ipow functions. These and others can be discussed in Portland; and I’ll be happy to add any functions, and make any name changes, that the committee would like.

This paper proposes that all operations eagerly normalize the fraction; but given that the rational class will use a bignum for its internal integer type, overflow is no longer a worry, and so it might be OK to add a mechanism for temporarily turning off normalization as suggested in N1718.

Text with a gray background is additional rationale in this document and is not intended as wording for the TS.

[rational.math] Rational math

 The header <rational> defines the rational class and several free functions and operators for doing arithmetic with rational numbers.

Header <rational> synopsis

namespace std {
namespace experimental { // subnamespace suggested in LWG in Kona
namespace rational {

class rational;

rational operator+(const rational& val);
rational operator-(const rational& val);

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

rational operator+(const rational& lhs, rational::int_type rhs);
rational operator-(const rational& lhs, rational::int_type rhs);
rational operator*(const rational& lhs, rational::int_type rhs);
rational operator/(const rational& lhs, rational::int_type rhs);

rational operator+(rational::int_type lhs, const rational& rhs);
rational operator-(rational::int_type lhs, const rational& rhs);
rational operator*(rational::int_type lhs, const rational& rhs);
rational operator/(rational::int_type lhs, const rational& rhs);

bool operator==(const rational& lhs, const rational& rhs);
bool operator!=(const rational& lhs, const rational& rhs);
bool operator< (const rational& lhs, const rational& rhs);
bool operator> (const rational& lhs, const rational& rhs);
bool operator<=(const rational& lhs, const rational& rhs);
bool operator>=(const rational& lhs, const rational& rhs);

bool operator==(const rational& lhs, rational::int_type rhs);
bool operator!=(const rational& lhs, rational::int_type rhs);
bool operator< (const rational& lhs, rational::int_type rhs);
bool operator> (const rational& lhs, rational::int_type rhs);
bool operator<=(const rational& lhs, rational::int_type rhs);
bool operator>=(const rational& lhs, rational::int_type rhs);

bool operator==(rational::int_type lhs, const rational& rhs);
bool operator!=(rational::int_type lhs, const rational& rhs);
bool operator< (rational::int_type lhs, const rational& rhs);
bool operator> (rational::int_type lhs, const rational& rhs);
bool operator<=(rational::int_type lhs, const rational& rhs);
bool operator>=(rational::int_type lhs, const rational& rhs);

void swap(rational& lhs, rational& rhs); 

rational::int_type floor(const rational& val);
rational::int_type ceil (const rational& val);
rational::int_type trunc(const rational& val);

enum rounding_mode
{
    nearest_even, nearest_odd,
    toward_pos_inf, toward_neg_inf,
    toward_zero, away_from_zero
};
rational::int_type nearest(const rational& val, rounding_mode mode = nearest_even);

rational::int_type round(const rational& val);

rational abs(const rational& val);

rational reciprocal(const rational& val);

rational ipow(const rational& val, int exp);

rational fmod(const rational& dividend, const rational& divisor);
rational remainder(const rational& dividend, const rational& divisor,
                   rounding_mode mode = nearest_even);

template<class intT>
  rational modf(const rational& val, intT* intptr);

rational modf(const rational& val);

template<class intT>
  rational remquo(const rational& dividend, const rational& divisor, intT* intptr,
                  rounding_mode mode = nearest_even);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    showden1(std::basic_ostream<charT,traits>& str);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    noshowden1(std::basic_ostream<charT,traits>& str);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    divalign(std::basic_ostream<charT,traits>& str);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    nodivalign(std::basic_ostream<charT,traits>& str);

template<class charT>
  implementation-detail setdiv(charT divsign);

template<class charT, class traits>
  std::basic_istream<charT,traits>&
    operator>>(std::basic_istream<charT,traits>& lhs, rational& rhs);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    operator<<(std::basic_ostream<charT,traits>& lhs, const rational& rhs);

} // namespace rational
} // namespace experimental
} // namespace std

[rational.class] Class rational

class rational {
public:
    typedef implementation-detail int_type;

    rational() noexcept;

    rational(const rational& rat) = default;

    explicit rational(char num) noexcept;
    explicit rational(signed char num) noexcept;
    explicit rational(unsigned char num) noexcept;
    explicit rational(char16_t num) noexcept;
    explicit rational(char32_t num) noexcept;
    explicit rational(wchar_t num) noexcept;
    explicit rational(short num) noexcept;
    explicit rational(unsigned short num) noexcept;
    explicit rational(int num) noexcept;
    explicit rational(unsigned num) noexcept;
    explicit rational(long num) noexcept;
    explicit rational(unsigned long num) noexcept;
    explicit rational(long long num) noexcept;
    explicit rational(unsigned long long num) noexcept;

    explicit rational(double val, double err = 1e-6);

    rational(int_type num, int_type den);

    ~rational() = default;

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

    rational& operator=(int_type num) noexcept;
    rational& assign(int_type num, int_type den);

    void swap(rational& rhs) noexcept;

    int_type numer() const noexcept;
    int_type denom() const noexcept;

    explicit operator bool() const noexcept;

    rational& negate() noexcept;
    rational& invert();

    rational& operator++();
    rational& operator--();

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

    rational& operator+=(int_type rhs);
    rational& operator-=(int_type rhs);
    rational& operator*=(int_type rhs);
    rational& operator/=(int_type rhs);

    rational& operator+=(const rational& rhs);
    rational& operator-=(const rational& rhs);
    rational& operator*=(const rational& rhs);
    rational& operator/=(const rational& rhs);
};
Class invariants: all constructors and operators shall eagerly normalize the value such that the numerator and denominator have no common factors other than 1 and the denominator is greater than zero. If the numerator is 0, the denominator shall be 1.

[rational.type] rational internal type:

typedef implementation-detail int_type;
This is the type that the rational class uses internally for its numerator and denominator. It shall be a signed unbounded integer type.

[rational.members] rational member functions:

rational() noexcept;
Effects: Constructs a rational with a value of zero.

Postcondition: numer() == 0 && denom() == 1.

rational(const rational& rat) = default;

Effects: Constructs a rational with a value of rat.

Postcondition: numer() == rat.numer() && denom() == rat.denom().

explicit rational(char num) noexcept;
explicit rational(signed char num) noexcept;
explicit rational(unsigned char num) noexcept;
explicit rational(char16_t num) noexcept;
explicit rational(char32_t num) noexcept;
explicit rational(wchar_t num) noexcept;
explicit rational(short num) noexcept;
explicit rational(unsigned short num) noexcept;
explicit rational(int num) noexcept;
explicit rational(unsigned num) noexcept;
explicit rational(long num) noexcept;
explicit rational(unsigned long num) noexcept;
explicit rational(long long num) noexcept;
explicit rational(unsigned long long num) noexcept;

The intent is that rationals can be explicitly constructed from all the built-in integer types except bool. Krügler suggests that we don’t need plain char, charN_t or wchar_t.

Effects: Constructs a rational with a value of num.

Postcondition: numer() == num && denom() == 1.

[Note: the implementation may provide additional overloads for <cstdint> types that are not just typedefs for fundamental integer types. — end note]

explicit rational(double val, double err = 1e-6);

Conversion from floating-point is probably a bad idea in general; but it seems like one of those things that, when you need it, you really need it; and folks who aren’t experts in numerics might not know how to write it. How the conversion is done is a quality-of-implementation issue. If numerics experts want a particular algorithm, they presumably know where to find it.

Effects: constructs a rational with a value approximately equal to val.

Postcondition: the value of *this shall be in the range, val * (1.0 ± err).

rational(int_type num, int_type den);

Requires: den != 0

Effects: Constructs a rational given the specified numerator and denominator and then enforces the class invariants.

Postcondition: *this == the mathematically correct num/den, numer() and denom() have no common factors other than 1, and denom() is greater than zero.

~rational() = default;

Effects: Destructs *this.

rational& operator=(int_type num) noexcept;

Effects: Assigns num to *this.

Postcondition: numer() == num && denom() == 1.

Returns: *this.

rational& assign(int_type num, int_type den);

Requires: den != 0

Effects: Assigns the specified numerator and denominator to *this and then enforces the class invariants.

Postcondition: *this == the mathematically correct num/den, numer() and denom() have no common factors other than 1, and denom() is greater than zero.

Returns: *this.

void swap(rational& rhs) noexcept;

Effects: Swaps *this and rhs.

Postcondition: *this == previous value of rhs; rhs == previous value of *this.

int_type numer() const noexcept;

Returns: the value of the numerator.

int_type denom() const noexcept;

Returns: the value of the denominator.

explicit operator bool() const noexcept;

Returns: numer() != 0.

rational& negate() noexcept;

Effects: changes the sign of the numerator.

Returns: *this.

rational& invert();

Effects: swaps the numerator and denominator, changing their signs if necessary to keep the denominator positive.

Requires: the numerator is non-zero.

Postcondition: denom() > 0.

Returns: *this.

[rational.member.ops] rational member operators:

rational& operator++();

Effects: adds 1 to *this and stores the result in *this.

Returns: *this.

rational& operator--();

Effects: subtracts 1 from *this and stores the result in *this.

Returns: *this.

rational operator++(int);

Effects: adds 1 to *this and stores the result in *this.

Returns: the value of *this before the addition.

rational operator--(int);

Effects: subtracts 1 from *this and stores the result in *this.

Returns: the value of *this before the subtraction.

rational& operator+=(int_type rhs);

Effects: adds the integer value rhs to *this and stores the result in *this.

Returns: *this.

rational& operator-=(int_type rhs);

Effects: subtracts the integer value rhs from *this and stores the result in *this.

Returns: *this.

rational& operator*=(int_type rhs);

Effects: multiplies *this by the integer value rhs and stores the result, reduced to lowest terms, in *this.

Returns: *this.

rational& operator/=(int_type rhs);

Effects: divides *this by the integer value rhs and stores the result, reduced to lowest terms, in *this.

Returns: *this.

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

Effects: adds the rational value rhs to *this and stores the result, reduced to lowest terms, in *this.

Returns: *this.

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

Effects: subtracts the rational value rhs from *this and stores the result, reduced to lowest terms, in *this.

Returns: *this.

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

Effects: multiplies *this by the rational value rhs and stores the result, reduced to lowest terms, in *this.

Returns: *this.

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

Effects: divides *this by the rational value rhs and stores the result, reduced to lowest terms, in *this.

Returns: *this.

[rational.ops] rational non-member operations:

rational operator+(const rational& val);

Returns: rational(val).

rational operator-(const rational& val);

Returns: rational(-val.numer(), val.denom()).

rational operator+(const rational& lhs, const rational& rhs);

Returns: rational(lhs) += rhs.

rational operator-(const rational& lhs, const rational& rhs);

Returns: rational(lhs) -= rhs.

rational operator*(const rational& lhs, const rational& rhs);

Returns: rational(lhs) *= rhs.

rational operator/(const rational& lhs, const rational& rhs);

Returns: rational(lhs) /= rhs.

rational operator+(const rational& lhs, rational::int_type rhs);

Returns: rational(lhs) += rhs.

rational operator-(const rational& lhs, rational::int_type rhs);

Returns: rational(lhs) -= rhs.

rational operator*(const rational& lhs, rational::int_type rhs);

Returns: rational(lhs) *= rhs.

rational operator/(const rational& lhs, rational::int_type rhs);

Returns: rational(lhs) /= rhs.

rational operator+(rational::int_type lhs, const rational& rhs);

Returns: rational(rhs) += lhs.

rational operator-(rational::int_type lhs, const rational& rhs);

Returns: rational(-rhs) += lhs.

rational operator*(rational::int_type lhs, const rational& rhs);

Returns: rational(rhs) *= lhs.

rational operator/(rational::int_type lhs, const rational& rhs);

Returns: rational(rhs).invert() *= lhs.

bool operator==(const rational& lhs, const rational& rhs);

Returns: lhs.numer() == rhs.numer() && lhs.denom() == rhs.denom().

bool operator!=(const rational& lhs, const rational& rhs);

Returns: !(lhs == rhs).

bool operator<(const rational& lhs, const rational& rhs);

Returns: lhs.numer() * rhs.denom() < rhs.numer() * lhs.denom().

bool operator>(const rational& lhs, const rational& rhs);

Returns: rhs < lhs.

bool operator<=(const rational& lhs, const rational& rhs);

Returns: !(rhs < lhs).

bool operator>=(const rational& lhs, const rational& rhs);

Returns: !(lhs < rhs).

bool operator==(const rational& lhs, rational::int_type rhs);

Returns: lhs.numer() == rhs && lhs.denom() == 1.

bool operator!=(const rational& lhs, rational::int_type rhs);

Returns: !(lhs == rhs).

bool operator<(const rational& lhs, rational::int_type rhs);

Returns: lhs.numer() < rhs * lhs.denom().

bool operator>(const rational& lhs, rational::int_type rhs);

Returns: lhs.numer() > rhs * lhs.denom().

bool operator<=(const rational& lhs, rational::int_type rhs);

Returns: !(rhs < lhs).

bool operator>=(const rational& lhs, rational::int_type rhs);

Returns: !(lhs < rhs).

bool operator==(rational::int_type lhs, const rational& rhs);

Returns: rhs == lhs.

bool operator!=(rational::int_type lhs, const rational& rhs);

Returns: rhs != lhs.

bool operator<(rational::int_type lhs, const rational& rhs);

Returns: rhs > lhs.

bool operator>(rational::int_type lhs, const rational& rhs);

Returns: rhs < lhs.

bool operator<=(rational::int_type lhs, const rational& rhs);

Returns: rhs >= lhs.

bool operator>=(rational::int_type lhs, const rational& rhs);

Returns: rhs <= lhs.

[rational.conv] rational numeric conversions:

rational::int_type floor(const rational& val);

Returns: the most positive integer not greater than val.

rational::int_type ceil(const rational& val);

Returns: the most negative integer not less than val.

rational::int_type trunc(const rational& val);

Returns: the integer part of val truncated toward zero. 

enum rounding_mode
{
    nearest_even, nearest_odd,
    toward_pos_inf, toward_neg_inf,
    toward_zero, away_from_zero
};
rational::int_type nearest(const rational& val, rounding_mode mode = nearest_even);

Returns: the integer nearest in value to val. If val.denom() == 2, the returned value shall be rounded as specified by mode. 

rational::int_type round(const rational& val);

Returns: nearest(val, away_from_zero)

[rational.swap] rational swap:

void swap(rational& lhs, rational& rhs) noexcept;

Effects: lhs.swap(rhs).

[rational.manip] I/O manipulators that apply to rational objects:

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    showden1(std::basic_ostream<charT,traits>& str);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    noshowden1(std::basic_ostream<charT,traits>& str);
These output manipulators control whether a denominator equal to 1 is written. If noshowden1 is in effect and the rational’s denominator equals 1, the output shall be just the numerator written as an ordinary rational::int_type. The default is noshowden1. 
template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    divalign(std::basic_ostream<charT,traits>& str);

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    nodivalign(std::basic_ostream<charT,traits>& str);
These output manipulators specify 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 aligning the division signs. The default is nodivalign.

[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.)
— end example] 
template<class charT>
  implementation-detail setdiv(charT divsign);
This I/O manipulator causes divsign to be used for the division sign. The default is stream.widen('/').

[rational.io] I/O operators that apply to rational objects:

template<class charT, class traits>
  std::basic_istream<charT,traits>&
    operator>>(std::basic_istream<charT,traits>& lhs, rational& rhs);
The extraction operator reads an integer value which it takes to be a numerator, and if that is immediately followed by a division sign, reads another integer value which it takes to be a denominator. If no division sign immediately follows the numerator, the denominator shall be assumed to be 1.

If the operator reads a value of zero when expecting a denominator, it shall set the stream’s failbit. If an ios_base::failure exception is thrown, or if the stream is not good() when the operator returns, rhs shall be untouched.

If the operator is successful, it shall have enforced the class invariants.

The stream’s locale and all its format flags except skipws shall apply separately to the numerator and the denominator. skipws shall apply to the numerator only.[footnote]

[footnote] Thus, if a denominator is present, the division sign must immediately follow the numerator, and the denominator must immediately follow the division sign, without any intervening characters including whitespace. 

template<class charT, class traits>
  std::basic_ostream<charT,traits>&
    operator<<(std::basic_ostream<charT,traits>& lhs, const rational& rhs);
The insertion operator shall write a rational to the specified output stream; and the numerator and denominator shall be written in whatever format is appropriate given the stream’s flags and locale. The showpos and showbase flags shall affect the numerator only.

[rational.over] Additional overloads:

rational abs(const rational& val);

Returns: rational(val) if val >= 0; otherwise -val.

rational reciprocal(const rational& val);

Returns: rational(val).invert().

rational ipow(const rational& val, int exp);

This is intended to be analagous to std::pow(double,double). The name, “ipow”, is intended to draw attention to the integer exponent requirement.

Returns: rational(1) if exp == 0; otherwise valexp.

Requires: val != 0 || exp >= 0.

Remarks: the exponent must be an integer since raising to a non-integer power yields an irrational value in general.

rational fmod(const rational& dividend, const rational& divisor);

This is intended to be analagous to std::fmod(double,double).

Returns: dividend - divisor * trunc(dividend / divisor). 
rational remainder(const rational& dividend, const rational& divisor,
                   rounding_mode mode = nearest_even);
This is intended to be analagous to std::remainder(double,double).
Returns: dividend - divisor * nearest(dividend / divisor, mode). 
template<class intT>
  rational modf(const rational& val, intT* intptr);
This is intended to be analagous to std::modf(double,double*).
Effects: if intptr is not a null pointer, *intptr shall be assigned trunc(val).

Returns: val - trunc(val).

rational modf(const rational& val);

This non-template one-argument overload is intended for users who want just the fractional part and don’t want to bother passing a null pointer to a template argument.

Returns: val - trunc(val). 
template<class intT>
  rational remquo(const rational& dividend, const rational& divisor, intT* intptr,
                  rounding_mode mode = nearest_even);
This is intended to be analagous to std::remquo(double,double,int*).
Effects: if intptr is not a null pointer, *intptr shall be assigned nearest(dividend / divisor, mode).

Returns: remainder(dividend, divisor, mode).

All suggestions and corrections will be welcome; all flames will be amusing.
Bill Seymour, <stdbill.h@pobox.com>.