N3489 - A Rational Number Library for C++

Doc No:	N3489 = 12-0179
Date:	2012-10-31
Reply to:	Bill Seymour, <stdbill`.`h^@pobox`.`com>

A Rational Number Library for C++

Bill Seymour
2012-10-31

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 N3414. Many thanks to Daniel Krügler for several excellent suggestions to get from the first version, N3363, to N3414.

This paper reflects several changes to N3414 suggested by the Numerics Study Group (SG-6) in Portland. These are:

replace all the one-argument constructors from integer types with just one taking a rational::int_type.
conversion from floating-point values can be exact.
remove the fmod, remainder and remquo functions.
change the name of the ipow function to just pow and fail to compile for non-integer exponents.

One additional change, not suggested by SG-6 but mentioned in N3414, is having a mechanism for temporarily turning off normalization as suggested in N1718. (Issue: should the comparison operators normalize the fraction so that they always give the right answer?)

A change suggested by SG-6 but not yet incorporated into this paper is using the rounding modes from Lawrence Crowl’s binary fixed-point paper for the second argument to the nearest function. Lawrence said that he will break that out into a separate paper. That change will probably appear in the pre-Bristol rational.

[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 for TRs 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, const rational::int_type& rhs);
rational operator-(const rational& lhs, const rational::int_type& rhs);
rational operator*(const rational& lhs, const rational::int_type& rhs);
rational operator/(const rational& lhs, const rational::int_type& rhs);

rational operator+(const rational::int_type& lhs, const rational& rhs);
rational operator-(const rational::int_type& lhs, const rational& rhs);
rational operator*(const rational::int_type& lhs, const rational& rhs);
rational operator/(const 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, const rational::int_type& rhs);
bool operator!=(const rational& lhs, const rational::int_type& rhs);
bool operator< (const rational& lhs, const rational::int_type& rhs);
bool operator> (const rational& lhs, const rational::int_type& rhs);
bool operator<=(const rational& lhs, const rational::int_type& rhs);
bool operator>=(const rational& lhs, const rational::int_type& rhs);

bool operator==(const rational::int_type& lhs, const rational& rhs);
bool operator!=(const rational::int_type& lhs, const rational& rhs);
bool operator< (const rational::int_type& lhs, const rational& rhs);
bool operator> (const rational::int_type& lhs, const rational& rhs);
bool operator<=(const rational::int_type& lhs, const rational& rhs);
bool operator>=(const 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);

template<class T> rational pow(const rational&, T) = delete;
template<> rational pow(const rational& val, const rational::int_type& exp);

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

rational modf(const rational& val);

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 {
    bool do_norm;  /* exposition only */

public:
    typedef implementation-detail int_type;

    rational() noexcept;

    rational(const rational& rat) = default;

    explicit rational(float num) noexcept;
    explicit rational(double num) noexcept;
    explicit rational(long double num) noexcept;

    explicit rational(const int_type& num);

    rational(const int_type& num, const int_type& den);

    ~rational() = default;

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

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

    void swap(rational& rhs) noexcept;

    void normalize(bool norm = true);

    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+=(const int_type& rhs);
    rational& operator-=(const int_type& rhs);
    rational& operator*=(const int_type& rhs);
    rational& operator/=(const 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 shall set do_norm to true; and if do_norm is true, all member functions that can mutate the value 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.

[Note: given the as-if rule, the copy constructor and copy-assignment operator don’t actually need to do any normalization; they just copy the numerator, denominator and do_norm flag verbatim. If do_norm is true, then presumably the value was already normalized anyway. — end note]

[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() && do_norm == rat.do_norm.

explicit rational(const int_type& num);

Effects: Constructs a rational with a value of num.
Postcondition: numer() == num && denom() == 1.

explicit rational(float num) noexcept;
explicit rational(double num) noexcept;
explicit rational(long double num) noexcept;

Effects: constructs a rational with a value equal to num.
Postcondition: static_cast<decltype(num)>(numer()) / static_cast<decltype(num)>(denom()) == num.

rational(const int_type& num, const int_type& den);

Requires: den != 0
Effects: Constructs a rational given the specified numerator and denominator.

~rational() = default;

Effects: Destructs *this.

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

Effects: Assigns rhs to *this.
Postcondition: numer() == rhs.numer() && denom() == rhs.denom() && do_norm == rhs.do_norm.
Returns: *this.

rational& operator=(const int_type& num) noexcept;

Effects: Assigns num to *this.
Postcondition: numer() == num && denom() == 1.
Returns: *this.

rational& assign(const int_type& num, const int_type& den);

Requires: den != 0
Effects: Assigns the specified numerator and denominator to *this.
Returns: *this.

void swap(rational& rhs) noexcept;

Effects: Swaps *this and rhs.
Postcondition: *this == previous value of rhs; rhs == previous value of *this.

void normalize(bool norm = true);

Effects: sets do_norm to norm.
Postcondition: if norm is true, numer() and denom() have no common factors other than 1, and denom() is greater than zero.

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+=(const int_type& rhs);

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

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

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

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

Effects: multiplies *this by the integer value rhs and stores the result in *this.
Returns: *this.

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

Effects: divides *this by the integer value rhs and stores the result in *this.
Returns: *this.

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

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

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

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

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

Effects: multiplies *this by the rational value rhs and stores the result in *this.
Returns: *this.

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

Effects: divides *this by the rational value rhs and stores the result 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, const rational::int_type& rhs);

Returns: rational(lhs) += rhs.

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

Returns: rational(lhs) -= rhs.

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

Returns: rational(lhs) *= rhs.

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

Returns: rational(lhs) /= rhs.

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

Returns: rational(rhs) += lhs.

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

Returns: rational(-rhs) += lhs.

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

Returns: rational(rhs) *= lhs.

rational operator/(const 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, const rational::int_type& rhs);

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

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

Returns: !(lhs == rhs).

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

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

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

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

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

Returns: !(rhs < lhs).

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

Returns: !(lhs < rhs).

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

Returns: rhs == lhs.

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

Returns: rhs != lhs.

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

Returns: rhs > lhs.

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

Returns: rhs < lhs.

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

Returns: rhs >= lhs.

bool operator>=(const 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 default is nodivalign. [Note: divalign is intended for printing fractions in columns by aligning the division signs. — end note]
[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().

template<class T> rational pow(const rational&, T) = delete;
template<> rational pow(const rational& val, const rational::int_type& exp);

Returns: rational(1) if exp == 0; otherwise val^exp.
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.

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

Effects: if intptr is not a null pointer, *intptr shall be assigned trunc(val).
Returns: val - trunc(val).

rational modf(const rational& val);

Returns: val - trunc(val).

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

A Rational Number Library for C++

Bill Seymour2012-10-31

Introduction:

[rational.math] Rational math

Header <rational> synopsis

[rational.class] Class rational

[rational.type] rational internal type:

[rational.members] rational member functions:

[rational.member.ops] rational member operators:

[rational.ops] rational non-member operations:

[rational.conv] rational numeric conversions:

[rational.swap] rational swap:

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

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