Doc No: N3611
Date: 2013-03-15
Reply to:  Bill Seymour, <stdbill.h@pobox.com>

A Rational Number Library for C++

Bill Seymour
2013-03-15


Introduction:

This paper proposes a rational number library for a C++ Technical Specification (TS).

Revision history:

Many thanks to Daniel Krügler for several excellent suggestions to get from N3363 to N3414.

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

A change suggested by SG-6 but not yet incorporated into this paper is using for the second argument to the nearest function the rounding modes from Lawrence Crowl’s N3352, C++ Binary Fixed-Point Arithmetic, Basic Operations. Lawrence said that he will break that out into a separate paper. That change will probably appear in this paper’s post-Bristol revision.

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.

N3489 asked whether the comparison operators should normalize the fraction so that they always give the right answer. Actually, this matters only for the == operators; and they can easily be written to work correctly if they know whether the rational is currently being normalized. To facilitate that, the normalizing() member function was added. (Note that this can’t be just a no-argument overload of the existing normalize() member function since that function’s only argument defaults.)

Also, I’ve decided that I like the seminumerical namespace in Pete Becker’s N3417.

Question: do we want conversion from fixed- and/or floating-point decimals? Fixed-point binary? I think all of them; but it’s not clear yet what will come out of SG-6 in this regard.

Question: do we want rational literals? I think not in general; and I echo the rationale in Pete Becker’s Open issue 7 in N3417 (they wouldn’t be constexpr). On the other hand, if Pete’s integer implements a small-integer optimization and has constexpr conversions from fundamental integer types, then maybe we could have literals for those rationals whose numerator and denominator can be represented in the fundamental types.

Issue: I still need to add move semantics.


[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 seminumerical {

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 integer& rhs);
rational operator-(const rational& lhs, const integer& rhs);
rational operator*(const rational& lhs, const integer& rhs);
rational operator/(const rational& lhs, const integer& rhs);

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

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

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

integer floor(const rational& val);
integer ceil (const rational& val);
integer trunc(const rational& val);

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

integer 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 integer& 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 seminumerical
} // namespace std

[rational.class] Class rational

class rational {
    bool do_norm; // exposition only

public:
    rational() noexcept;

    rational(const rational& rat) = default;

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

    explicit rational(const integer& num);

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

    ~rational() = default;

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

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

    void swap(rational& rhs) noexcept;

    void normalize(bool norm = true) noexcept;
    bool normalizing() const noexcept;

    const integer& numer() const noexcept;
    const integer& 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 integer& rhs);
    rational& operator-=(const integer& rhs);
    rational& operator*=(const integer& rhs);
    rational& operator/=(const integer& rhs);

    rational& operator+=(const rational& rhs);
    rational& operator-=(const rational& rhs);
    rational& operator*=(const rational& rhs);
    rational& operator/=(const rational& rhs);
};
The numerator and denominator shall be stored internally in a std::seminumerical::integer.

Class invariants: all constructors except the copy constructor 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.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 integer& num);

Effects: Constructs a rational with a value of num.

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

explicit rational(float val);
explicit rational(double val);
explicit rational(long double val);

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

Postcondition: static_cast<decltype(val)>(numer()) / static_cast<decltype(val)>(denom()) == val.

rational(const integer& num, const integer& 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 integer& num) noexcept;

Effects: Assigns num to *this.

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

Returns: *this.

rational& assign(const integer& num, const integer& 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) noexcept;

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.

bool normalizing() const noexcept;

Returns: do_norm.

const integer& numer() const noexcept;

Returns: a const reference to the numerator.

const integer& denom() const noexcept;

Returns: a const reference to 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 integer& rhs);

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

Returns: *this.

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

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

Returns: *this.

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

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

Returns: *this.

rational& operator/=(const integer& 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 integer& rhs);

Returns: rational(lhs) += rhs.

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

Returns: rational(lhs) -= rhs.

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

Returns: rational(lhs) *= rhs.

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

Returns: rational(lhs) /= rhs.

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

Returns: rational(rhs) += lhs.

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

Returns: rational(-rhs) += lhs.

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

Returns: rational(rhs) *= lhs.

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

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

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

Returns: !(lhs == rhs).

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

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

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

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

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

Returns: !(rhs < lhs).

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

Returns: !(lhs < rhs).

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

Returns: rhs == lhs.

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

Returns: rhs != lhs.

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

Returns: rhs > lhs.

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

Returns: rhs < lhs.

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

Returns: rhs >= lhs.

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

Returns: rhs <= lhs.

[rational.conv] rational numeric conversions:

integer floor(const rational& val);

Returns: the most positive integer not greater than val.

integer ceil(const rational& val);

Returns: the most negative integer not less than val.

integer 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
};
integer 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.

integer 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 integer. 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 integer& exp);
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.

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>.