A few features:
The rational class is not thread-safe, and a single instance may not appear in multiple threads if it gets modified in any of them. This includes exposing the value to the outside world which first reduces the fraction to its lowest terms. |
The files distributed with the library are:
The code can be compiled with any C++ implementation that conforms at least to C++11.
As of this writing, the author is still completing his testing.
Static link libraries with both rational and bigint objects for both Linux and Windows are coming Real Soon Now. |
#include "bigint.hpp" namespace rat { using dbacc::bigint; // // The rational Class // class rational final { public: // // Special Member Functions and swap() // rational(); ~rational() noexcept; rational(const rational&); rational(rational&&); rational& operator=(const rational&); rational& operator=(rational&&); void swap(rational&); // // Construction from Other Types // (SFINAE for templates not shown) // template<typename intT> rational(intT); template<typename numT, typename denT> rational(numT, denT); rational(const bigint&); rational(bigint&&); rational(const bigint&, const bigint&); rational(bigint&&, bigint&&); template<typename floatT> explicit rational(floatT, long double accuracy = 0.0); explicit rational(const char*, int radix = 0, const char** = nullptr); explicit rational(const std::string&, int radix = 0, std::size_t* = nullptr); // // Assignment from Other Types // (SFINAE for templates not shown) // template<typename intT> rational& operator=(intT); template<typename numT, typename denT> rational& assign(numT, denT); rational& operator=(const bigint&); rational& operator=(bigint&&); rational& assign(const bigint&, const bigint&); rational& assign(bigint&&, bigint&&); template<typename floatT> rational& assign(floatT, long double accuracy = 0.0); rational& assign(const char*, int radix = 0, const char** = nullptr); rational& assign(const std::string&, int radix = 0, std::size_t* = nullptr); // // Observers // const bigint& numer() const noexcept; const bigint& denom() const noexcept; bool is_zero() const noexcept; bool is_neg() const noexcept; bool is_pos() const noexcept; bool is_one() const noexcept; bool is_one(bool negative) const noexcept; bool is_norm() const noexcept; explicit operator bool() const noexcept; explicit operator long double() const; std::string to_string(int radix = 10) const; int compare(const rational&) const; int signum() const noexcept; // // Mutators // rational& set_to_zero(); rational& set_to_one(bool negative = false); rational& negate() noexcept; rational& abs() noexcept; rational& invert(); const rational& normalize() const; // // Arithmetic Operators // rational& operator++(); rational& operator--(); rational operator++(int); rational operator--(int); rational& operator+=(const rational&); rational& operator-=(const rational&); rational& operator*=(const rational&); rational& operator/=(const rational&); // // Heap Usage // std::size_t size() const noexcept; std::size_t capacity() const noexcept; void shrink_to_fit(); }; // // Non-member Functions // using std::swap; void swap(rational&, rational&); std::string to_string(const rational&, int radix = 10); rational reciprocal(const rational&); // // Comparisons // bool operator==(const rational&, const rational&); bool operator!=(const rational&, const rational&); bool operator< (const rational&, const rational&); bool operator> (const rational&, const rational&); bool operator<=(const rational&, const rational&); bool operator>=(const rational&, const rational&); // // Non-member Arithmetic Operators // rational operator+(const rational&); rational operator-(const rational&); rational operator+(const rational&, const rational&); rational operator-(const rational&, const rational&); rational operator*(const rational&, const rational&); rational operator/(const rational&, const rational&); // // A Few <cmath>-like Functions // enum rounding // for rounding rationals to integer values { all_to_neg_inf, all_to_pos_inf, all_to_zero, all_away_zero, all_to_even, all_to_odd, all_fastest, all_smallest, all_unspecified, tie_to_neg_inf, tie_to_pos_inf, tie_to_zero, tie_away_zero, tie_to_even, tie_to_odd, tie_fastest, tie_smallest, tie_unspecified }; rational abs(const rational&); rational round(const rational&, rounding = tie_away_zero); rational ceil(const rational&); rational floor(const rational&); rational trunc(const rational&); rational rint(const rational&); rational modf(const rational&, rational* int_part = nullptr); rational fmod(const rational&, const rational&); rational remainder(const rational&, const rational&, rounding = tie_to_even); rational sqr(const rational&); rational pow(const rational&, int); rational copysign(const rational&, const rational&); rational fma(const rational&, const rational&, const rational&); // // I/O Operators // template<typename Ch, typename Tr> std::basic_istream<Ch,Tr>& operator>>(std::basic_istream<Ch,Tr>&, rational&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& operator<<(std::basic_ostream<Ch,Tr>&, const rational&); // //I/O Manipulators // template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& showden1(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& noshowden1(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& divalign(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& nodivalign(std::basic_ostream<Ch,Tr>&); template<typename Ch> implementation-detail setdiv(Ch); } // namespace rat
The rational Class
Since basically every operation on rational numbers requires multiplication behind the scenes,
numerators and denominators can get big in a hurry. To mitigate the overflow problem,
the class is implemented internally using
an unbounded integer
for the numerator and denominator.
The class provides implicit conversion from all built-in integers and the bigint type used internally; but it provides only explicit conversion between rationals and built-in floating point values since the principal use for rational numbers is doing arithmetic exactly, but floating point types are inexact in general.
Explicit conversion between rationals and strings is also provided. The strings may contain octal, decimal or hexadecimal representations.
The class has no NaNs or infinities, so rationals are strongly ordered.
Class invariants: the class will never represent a negative zero, the denominator will always be greater than zero, and if the numerator is zero the denominator is 1.
Construction and assignment will eagerly normalize the fraction such that the numerator and denominator have no common factor other than 1, but at other times the numerator and denominator are allowed to grow without bound. There’s a normalize() function that users can call if they think it’s time to try to normalize the fraction, but nothing in the library uses it except during construction and assignment or when the value becomes externally visible.
Issues:
|
rational();
The default constructor creates a rational with a numerator equal to 0 and a denominator equal to 1.
~rational() noexcept;
The destructor is non-trivial.
rational(const rational&); rational(rational&&); rational& operator=(const rational&); rational& operator=(rational&&); void swap(rational&);
rationals are freely copyable, moveable and swappable.
template<typename intT> rational(intT); template<typename numT, typename denT> rational(numT, denT);
A rational may be implicitly constructed from a value of any built-in integer type, and it may be constructed from a pair of built-in integers representing the desired numerator and denominator respectively.
These constructors actually use SFINAE to assure that all arguments are built-in integers. The details aren’t documented here because they would just obscure the high-level purpose of these constructors. C++ coders who are familiar with type traits templates will likely find the details unsurprising (and probably tedious as well).
rational(const bigint&); rational(bigint&&); rational(const bigint&, const bigint&); rational(bigint&&, bigint&&);
A rational may also be implicitly constructed from a bigint, and it may be constructed from a pair of bigints representing the desired numerator and denominator respectively.
template<typename floatT> explicit rational(floatT value, long double accuracy = 0.0);
A rational may be explicitly constructed from a value of built-in floating point type. (Implicit construction is not allowed because the whole point of doing rational arithmetic is to do it exactly, and floating point types are inexact in general.) As with the constructors that take built-in integers, SFINAE assures that floatT will be float, double or long double.The optional second argument can be used to control how accurate the conversion is. For example, if ±0.1% of value is good enough, you can explicitly pass 0.001. If you explicitly pass zero, or if you let the argument default to that, the conversion will be exact (in which case you’ll likely get very large numerators and denominators, and the author’s implementation takes almost 6µs to convert DBL_MAX to rational).
This constructor will throw an invalid_argument exception if value is a floating point NaN or infinity.
As currently written, it can also throw a logic_error if it can’t exit its continued fractions loop because the value is no longer converging. The author doesn’t believe that that can actually happen even if zero is passed as the second argument: value is a floating point number, not a real number, and so an exact rational equivalent exists; but he’s not good enough at numerics to prove that the continued fractions algorithm can find the value in all cases, so the code to check for that is there just in case.
explicit rational(const char* value, int radix = 0, const char** termchr = nullptr); explicit rational(const std::string& value, int radix = 0, std::size_t* termpos = nullptr);
A rational may also be explicitly constructed from a string. The first of these two functions will throw an invalid_argument if value is nullptr, and either will throw an invalid_argument if the string is not in one of the recognized forms, if the string contains no digit at all, or if the denominator is zero.The string may optionally begin with a '+' or a '-' followed by one of:
- integer
- integer-numerator '/' integer-denominator
- integeropt '.' integeropt exponentopt
If the string contains a '.', it will be taken to be a single number in either fixed point or scientific notation, but hexadecimal strings are not allowed in scientific notation (because an 'E' or 'e' would just be a digit, never the beginning of an exponent). There must be at least one digit either before or after the '.'.
At present, the functions recognize commas as thousands separators for users who think that that would make their code more readable, but any ',' will just be ignored. There’s no requirement that they be in the right places. Octal, decimal and hexadecimal strings are supported. Hexadecimal digits may be any combination of upper or lower case.
If radix is not one of 8, 10 or 16 (and note that it defaults to 0):
- If the number begins with "0X" or "0x", the radix will be 16.
- If the number begins with '0' not followed by 'X' or 'x', the radix will be 8.
- Otherwise, the radix will be 10.
If the function encounters any character that’s not a proper digit for the selected radix (except for the optional sign, base, comma, slash or period), it will just terminate the parse; and so the number may be part of a larger string as long as the number begins the string.
The optional third argument may be used to discover the character that terminated the parse:
- If termchr is not nullptr, *termchr will be assigned a pointer to the character that terminated the parse, which will be a pointer to a '\0' if the function reached the end of the string.
- If termpos is not nullptr, *termpos will be assigned the position of the character that terminated the parse, which will be value.size() if the function reached the end of the string.
template<typename intT> rational& operator=(intT); template<typename numT, typename denT> rational& assign(numT, denT); rational& operator=(const bigint&); rational& operator=(bigint&&); rational& assign(const bigint&, const bigint&); rational& assign(bigint&&, bigint&&); template<typename floatT> rational& assign(floatT, long double = 0.0); rational& assign(const char*, int = 0, const char** = nullptr); rational& assign(const std::string&, int = 0, std::size_t* = nullptr);
All assignment functions have the same semantics as do their corresponding constructors (including SFINAE, not shown, for the three templates). All return *this.
const bigint& numer() const noexcept; const bigint& denom() const noexcept;
These functions return the (possibly unnormalized) numerator and denominator respectively.
bool is_zero() const noexcept; bool is_neg() const noexcept; bool is_pos() const noexcept;
is_zero() returns whether *this == 0.
is_neg() returns whether *this < 0.
is_pos() returns whether *this > 0.
These are more efficient than comparing *this to the integer 0.
bool is_one() const noexcept; bool is_one(bool negative) const noexcept;
is_one() with no argument returns whether *this is ±1.
is_one(false) returns whether *this is +1.
is_one(true) returns whether *this is −1.
These are more efficient than comparing *this to the integer 1.
bool is_norm() const noexcept;
This function returns true if it’s known that the numerator and denominator have no common factor other than 1. If it returns false, that state is unknown.
explicit operator bool() const noexcept;
This is intended to support the “if (my_rat)” idiom. It returns!this->is_zero().
explicit operator long double() const;
This calls normalize() to lessen the chance of overflow and returns long double(numer()) / long double(denom()).If either the numerator or the denominator overflows a long double, this function will normally throw an overflow_error; but see the caveats with a yellow background in the bigint documentation. (It’s the bigint class that actually throws the exception.)
std::string to_string(int radix = 10) const;
This function calls normalize() and then returns a string, possibly beginning with '-' (but never '+'), followed immediately by the numerator, followed immediately by '/', followed immediately by the denominator. The numerator and denominator will be written as appropriate for the requested radix. Only octal, decimal and hexadecimal representations are supported; and if radix is not one of 8, 10 or 16, it will default to 10. Hexadecimal digits will be upper case. There will be no leading '0' or "0X" to indicate the radix. If you want something fancier, you can write to a std::basic_ostringstream<>.
int compare(const rational& rhs) const;
This function returns a value less than zero if *this < rhs, zero if *this == rhs, or a value greater than zero if *this > rhs.
int signum() const noexcept;
This function returns −1 if this->is_neg(), 0 if this->is_zero(), or +1 if this->is_pos().
rational& set_to_zero(); rational& set_to_one(bool negative = false);
set_to_zero() assigns 0 to *this.
set_to_one(false) assigns +1 to *this.
set_to_one(true) assigns −1 to *this.
These are more efficient than the assignment operator.
rational& negate() noexcept;
This function changes the sign of *this if !this->is_zero(). It will never create a negative zero.
This is more efficient than the non-member unary − operator.
rational& abs() noexcept;
This function sets *this to its absolute value.
rational& invert();
This function throws a domain_error exception if the numerator is zero; otherwise it swaps the numerator and denominator, possibly changing the sign of both to guarantee a denominator greater than zero.
const rational& normalize() const;
This function normalizes the fraction such that the numerator and denominator have no common factor other than 1.
Tricky code: normalize() is declared to be a const member function because the numerical value of the object doesn’t change, although it does change the internal representation, and so the values returned by numer(), denom() and is_norm() could change. *this is returned by const reference so that we can’t unintentionally play any other tricks later.The library doesn’t make use of this except during construction and assignment from other types or when the value becomes externally visible, and so the numerator and denominator are normally allowed to grow without bound; but users can call this function if they think that memory usage is getting out of hand (for example, after doing lots of arithmetic which almost certainly requires multiplication behind the scenes).
All of these functions return *this.
rational& operator++(); rational& operator--(); rational operator++(int); rational operator--(int); rational& operator+=(const rational&); rational& operator-=(const rational&); rational& operator*=(const rational&); rational& operator/=(const rational&);
The bigint class used for the numerator and denominator is implemented in terms of a std::vector<some built-in unsigned integer type>. The element type can vary depending on the C++ implementation that you’ve used to compile the code.
std::size_t size() const noexcept; std::size_t capacity() const noexcept;
These functions return the total number of bytes used for the numerator and denominator.If you’d like more detailed information about heap usage, you can call any of numer().size(), numer().capacity(), denom().size() or denom().capacity(). Those bigint member functions have the same semantics as do vector’s functions of the same names, except that the returned values are numbers of bytes, not numbers of container elements (because we’re not sure what the element type is).
void shrink_to_fit();
This function just calls shrink_to_fit() on both the numerator and the denominator.
using std::swap; void swap(rational& lhs, rational& rhs);
As if: lhs.swap(rhs);
std::string to_string(const rational& val, int radix = 10);
As if: return val.to_string(radix);
rational reciprocal(const rational& val);
As if: return rational(val).invert();
bool operator==(const rational&, const rational&); bool operator!=(const rational&, const rational&); bool operator< (const rational&, const rational&); bool operator> (const rational&, const rational&); bool operator<=(const rational&, const rational&); bool operator>=(const rational&, const rational&);
Since rationals have no NaN or infinity values, they’re strongly ordered.
rational operator+(const rational&); rational operator-(const rational&); rational operator+(const rational&, const rational&); rational operator-(const rational&, const rational&); rational operator*(const rational&, const rational&); rational operator/(const rational&, const rational&);
Also supplied are rounding modes for use when rounding rationals to integers.
enum rounding { all_to_neg_inf, all_to_pos_inf, all_to_zero, all_away_zero, all_to_even, all_to_odd, all_fastest, all_smallest, all_unspecified, tie_to_neg_inf, tie_to_pos_inf, tie_to_zero, tie_away_zero, tie_to_even, tie_to_odd, tie_fastest, tie_smallest, tie_unspecified };
The rounding modes are borrowed from WG21’s P1889R1 §3.3. Note that it’s an unscoped enumeration, so the enumerators are in the rat namespace. All of the …fastest, …smallest and …unspecified modes behave like their corresponding …to_zero modes.
rational abs(const rational&); rational round(const rational&, rounding = tie_away_zero); rational ceil(const rational&); rational floor(const rational&); rational trunc(const rational&); rational rint(const rational&); rational modf(const rational&, rational* int_part = nullptr); rational fmod(const rational&, const rational&); rational remainder(const rational&, const rational&, rounding = tie_to_even); rational sqr(const rational&); rational pow(const rational&, int); rational copysign(const rational&, const rational&); rational fma(const rational&, const rational&, const rational&);
Note that a rounding mode may be passed to rat::round(). The default, tie_away_zero, mimics std::round().Similarly, a rounding mode may be passed to rat::remainder(). The default, tie_to_even, mimics std::remainder().
The second argument to modf() can be nullptr, and defaults to nullptr, in which case the function will just return the fractional part of the value.
Note that the exponent to rat::pow() must be an integer since raising to a non-integer power yields an irrational value in general.
rat::fma() doesn’t do anything special since no rounding would occur between the multiplication and the addition in any event; but it’s included because it’s canonical, and it could help with converting existing code to use rationals instead of floating point types. The standard FP_FAST_FMA macro tells you nothing about this function.
The division sign will be whatever character, narrow or wide, has been set by the
template<typename Ch, typename Tr> std::basic_istream<Ch,Tr>& operator>>(std::basic_istream<Ch,Tr>&, rational&);
Leading whitespace will be ignored if skipws is in effect, then the input may be either a single integer (which will be the numerator and the denominator will be one), or two integers separated by a division sign (in which case the first will be the numerator and the second the denominator).
A denominator may optionally begin with a '+' or '-'. H. sapiens would probably never write that, but it’s not hard to imagine machine-generated strings coming out that way. In any event, assigning the value to the right-hand operand will enforce the class invariant that the denominator always be greater than zero. If the operator reads a value of zero when expecting a denominator, it will set the stream’s failbit which could throw an ios_base::failure if the user has set up the stream to do so. If the exception is thrown, or if the stream is not
good() when the operator returns, the operator might have removed a number of characters from the stream; but the rational on the right-hand side will be untouched.The stream’s locale and all its format flags except skipws apply separately to the numerator and the denominator. skipws applies to the numerator only; so there may be no whitespace between the numerator, the division sign, and the denominator.
The oct, dec and hex flags are the only way to select the radix. There’s no way to override them by including an indication of the base in the string. (Hexadecimal input may begin with "0X" or "0x", but it will just be ignored.)
At present, the operator recognizes localized thousands separators but just ignores them. It doesn’t require that they be in the right places.
template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& operator<<(std::basic_ostream<Ch,Tr>&, const rational&);
The insertion operator normalizes its right-hand operand and writes a rational to the specified output stream, the numerator and denominator being written in whatever format is appropriate given the stream’s flags and locale. The showpos and showbase flags affect the numerator only.The output will be an optional sign or base, followed by the numerator, followed (usually immediately) by a division sign, followed immediately by the denominator. If the denominator is 1, output of the division sign and the '1' can be suppressed with the noshowden1 manipulator described below (and noshowden1 is the default).
template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& showden1(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& noshowden1(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& divalign(std::basic_ostream<Ch,Tr>&); template<typename Ch, typename Tr> std::basic_ostream<Ch,Tr>& nodivalign(std::basic_ostream<Ch,Tr>&);
Two new pairs of no-argument output manipulators provide additional formatting options when writing rationals.
showden1 and noshowden1 control whether a denominator equal to 1 is written. If noshowden1 is in effect and the denominator is 1, neither the division sign nor the '1' will be written; so the output will be just the numerator written as an ordinary integer.
divalign and nodivalign control 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 lining up the division signs.
The defaults are noshowden1 and nodivalign.
For 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.)
template<typename Ch> implementation-detail setdiv(Ch);
This one-argument I/O manipulator sets the character to be used for the division sign. For example:cout << setdiv('÷') << rational(1,3);yields the output:1÷3As expected, the default division sign isstream.widen('/').
All these manipulators call Note that the compiler can’t find any of these manipulators by argument-dependent lookup (ADL); so you’ll need to either explicitly qualify their use with the rat namespace or have a using declaration for them. |
The actual code in rational.hpp is:
} // end of namespace rat #ifndef RATIONAL_NO_IO_OPERATORS #include "rational_io.hpp" #endifand rational_io.hpp contains the actual template definitions in the rat namespace. The hope is that the compiler’s lexer won’t even have to scan that code if it doesn’t need to. rational_io.hpp is a proper header file beginning and ending in the global namespace,
and with the usual include guard. If you include rational.hpp
with RATIONAL_NO_IO_OPERATORS defined, you can still get the I/O operators later
in the same TU by explicitly including rational_io.hpp yourself. It’s
not clear why you’d want to do that, but there it is.
|