Doc No: | N3611 |
Date: | 2013-03-15 |
Reply to: | Bill Seymour, <stdbill.h@pobox.com> |
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
A change suggested by
One additional change, not suggested by
N3489 asked whether the comparison operators should normalize the fraction
so that they always give the right answer. Actually, this matters only for the
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
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.
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
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]
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 != 0Effects: 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 != 0Effects: 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& 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 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.
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)
void swap(rational& lhs, rational& rhs) noexcept;
Effects: lhs.swap(rhs).
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 isstream.widen('/').
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 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).