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