pgl::Rational< Int > Class Template Reference

Exact rational number class template. More...

#include <rational.hpp>

Inheritance diagram for pgl::Rational< Int >:

Public Member Functions
constexpr	Rational ()
	Default constructor (0).
constexpr	Rational (RationalConcept auto n)
	Construct from another Rational.
constexpr	Rational (pgl::detail::extended_integral auto n)
	Construct from integer.
template<std::same_as< Int > T> requires (!pgl::detail::extended_integral<Int> && !std::floating_point<Int> && !RationalConcept<Int>)
constexpr	Rational (T n)
	Construct from a numerator of the rational's own integer type (denominator 1), covering integer types not matched by the overloads above, such as BigInt.
constexpr	Rational (Int n, Int d, bool normalized=false)
	Construct from numerator and denominator.
template<std::floating_point Float>
constexpr	Rational (Float f, int digits=pgl::detail::numeric_limits< Int >::digits > 0 ? std::min(pgl::detail::numeric_limits< Float >::digits, pgl::detail::numeric_limits< Int >::digits/2 - 4) :pgl::detail::numeric_limits< Float >::digits)
	Construct from floating point.
constexpr Int	numerator () const noexcept
	Get numerator (in lowest terms).
constexpr Int	denominator () const noexcept
	Get denominator (in lowest terms).
constexpr void	simplify ()
	Reduces the stored fraction to lowest terms in place (den stays > 0).
constexpr Rational	simplified () const
	Returns this value reduced to lowest terms.
constexpr void	simplifyIfLarge ()
	Reduces in place, but only when the stored parts have already grown wide enough that the next arithmetic step would reduce them anyway.
constexpr Rational	simplifiedIfLarge () const
	Returns this value reduced, but only when it is already wide enough that the next arithmetic step would reduce it anyway.
constexpr bool	isInteger () const
	Whether this rational is exactly an integer.
constexpr	operator float () const
	Convert to float.
constexpr	operator double () const
	Convert to double.
constexpr	operator long double () const
	Convert to long double.
constexpr	operator int () const
	Convert (truncating toward zero) to int.
constexpr	operator int64_t () const
	Convert (truncating toward zero) to int64_t. Divides first, for the reason given on operator int() const.
constexpr	operator Int () const
	Convert (truncating toward zero) to the numerator integer type, for Int types not already covered by operator int/operator int64_t above, such as BigInt. den > 0 is an invariant, so the truncating division num / den matches truncating the exact value regardless of whether the fraction is stored reduced.
template<class OtherInt>
constexpr	operator Rational< OtherInt > () const
	Convert to another Rational.
template<std::floating_point Float = double>
constexpr Float	lowerBound () const
	Computes a monotone, downward-rounded floating-point approximation of num / den.
template<std::floating_point Float = double>
constexpr Float	upperBound () const
	Computes a monotone, upward-rounded floating-point approximation of num / den.
constexpr bool	safeRaw () const
	Whether the raw num/den can be combined as-is without first reducing (i.e. already normalized, or small enough to be safe).
constexpr Rational	operator+ (const Rational &r) const
constexpr Rational	operator- (const Rational &r) const
constexpr Rational< Int >	operator* (const Rational< Int > &r) const
constexpr Rational	reciprocal () const
constexpr Rational	operator/ (const Rational &r) const
constexpr Rational	operator- () const
constexpr Rational &	operator+= (const Rational &r)
constexpr Rational &	operator-= (const Rational &r)
constexpr Rational &	operator*= (const Rational &r)
constexpr Rational &	operator/= (const Rational &r)
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr Rational	operator+ (const I &x) const
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr Rational	operator- (const I &x) const
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr Rational	operator* (const I &x) const
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr Rational	operator/ (const I &x) const
constexpr std::strong_ordering	operator<=> (const Rational &r) const
	Three-way comparison operator.
template<class U> requires (!std::same_as<U, Int>)
constexpr std::strong_ordering	operator<=> (const Rational< U > &r) const
	Three-way comparison against a Rational of a different integer type.
constexpr bool	operator== (const Rational &r) const
	Equality comparison.
constexpr bool	operator!= (const Rational &r) const
template<class U> requires (!std::same_as<U, Int>)
constexpr bool	operator== (const Rational< U > &r) const
	Equality comparison against a Rational of a different integer type.
template<std::floating_point Float>
std::partial_ordering	operator<=> (Float f) const
	Exact three-way comparison against a floating-point value (partial: NaN compares unordered).
template<std::floating_point Float>
bool	operator== (Float f) const
	Exact equality against a floating-point value.
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr std::strong_ordering	operator<=> (const I &n) const
	Exact three-way comparison against an integer value.
template<class I> requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)
constexpr bool	operator== (const I &n) const
	Exact equality against an integer value.
constexpr Rational &	operator++ ()
constexpr Rational	operator++ (int)
constexpr Rational &	operator-- ()
constexpr Rational	operator-- (int)

Static Public Member Functions
template<class A, class B>
static constexpr std::strong_ordering	compareValues (const A &a, const B &b)
	Three-way ordering of two values.
template<class I>
static constexpr bool	isNegativeOne (const I &n)
	Whether an integer argument is exactly -1.

Friends
constexpr Rational	operator+ (Int x, const Rational &r)
constexpr Rational	operator- (Int x, const Rational &r)
constexpr Rational	operator* (Int x, const Rational &r)
constexpr Rational	operator/ (Int x, const Rational &r)
std::ostream &	operator<< (std::ostream &os, const Rational &r)
	Output format: num/den or just num if den==1.
std::istream &	operator>> (std::istream &is, Rational &r)
	Input format: num/den or integer.

Detailed Description

template<class Int = int64_t>
class pgl::Rational< Int >

Exact rational number class template.

A class representing rational numbers (fractions).

Forward declaration of the exact rational number class.

Template Parameters

T	Integral storage type.

The Rational class stores a fraction as numerator/denominator using an integral type Int. The fraction is always normalized:

• gcd(num, den) == 1
• den > 0

Template Parameters

Int	Integral type used for storage.

Constructor & Destructor Documentation

Rational() [1/6]

template<class Int = int64_t>

pgl::Rational< Int >::Rational ( )

inlineconstexpr

Default constructor (0).

Rational() [2/6]

template<class Int = int64_t>

pgl::Rational< Int >::Rational ( RationalConcept auto n )

inlineconstexpr

Construct from another Rational.

The source is taken by value and simplified once, rather than read through numerator() and denominator(): those each run their own gcd over the same deferred pair, so reading both that way reduces it twice.

Rational() [3/6]

template<class Int = int64_t>

pgl::Rational< Int >::Rational ( pgl::detail::extended_integral auto n )

inlineconstexpr

Construct from integer.

Rational() [4/6]

template<class Int = int64_t>

template<std::same_as< Int > T>
requires (!pgl::detail::extended_integral<Int> && !std::floating_point<Int> && !RationalConcept<Int>)

pgl::Rational< Int >::Rational ( T n )

inlineconstexpr

Construct from a numerator of the rational's own integer type (denominator 1), covering integer types not matched by the overloads above, such as BigInt.

The parameter is templated on std::same_as<Int> rather than written as a plain Rational(Int) so that Int is not deducible from the argument, which keeps this constructor's synthesized implicit deduction guide from ever picking Int off the argument during CTAD. A plain Rational(Int) guide, constrained only by a requires-clause, is mishandled by clang 18: it fails to drop the guide for floating-point and so deduces Rational<double> for a bare Rational(5.25). With Int non-deducible here, the intended CTAD is pinned by the explicit guides declared after the class instead. See Rational deduction guides.

Rational() [5/6]

template<class Int = int64_t>

pgl::Rational< Int >::Rational ( Int n, Int d, bool normalized = false )

inlineconstexpr

Construct from numerator and denominator.

Rational() [6/6]

template<class Int = int64_t>

template<std::floating_point Float>

pgl::Rational< Int >::Rational ( Float f, int digits = pgl::detail::numeric_limits<Int>::digits, 0 ? std::min(pgl::detail::numeric_limits< Float >::digits, pgl::detail::numeric_limits< Int >::digits/2 - 4) :pgl::detail::numeric_limits< Float >::digits  )

inlineexplicitconstexpr

Construct from floating point.

Keeps digits significant bits of f: the integer part exactly, and as many bits of the fraction as fit beside it, the rest truncated. Once the integer part alone needs every one of those bits, or more, the value is truncated toward zero to that integer part, which is what a plain integer conversion does; only an integer part that Int cannot hold is refused, as is a value that is not finite.

The default digits is half the width of a bounded Int, less a few bits, so that the parts leave room for the arithmetic that follows.

Exceptions

std::domain_error	If f is infinite or NaN.
std::overflow_error	If the integer part of f does not fit Int.

Member Function Documentation

compareValues()

template<class Int = int64_t>

template<class A, class B>

constexpr std::strong_ordering pgl::Rational< Int >::compareValues ( const A & a, const B & b )

inlinestaticconstexpr

Three-way ordering of two values.

Uses the native operator<=> when the storage type provides it (e.g. __int128_t), and otherwise derives the ordering from < for types that lack three-way comparison (e.g. Boost.Multiprecision numbers, used as the int128 fallback).

The three-way operator is taken only when it is exact, which is what requiring a std::strong_ordering result checks. A mixed comparison of a built-in integer against the Boost int128 fallback would otherwise be answered by the int128-versus-double operator declared in numeric.hpp (found as a reversed candidate, with the integer converted to double): it reports std::partial_ordering, and it rounds. Such a pair falls back to <, which Boost defines exactly for every mixed integer operand.

denominator()

template<class Int = int64_t>

Int pgl::Rational< Int >::denominator ( ) const

inlineconstexprnoexcept

Get denominator (in lowest terms).

isInteger()

template<class Int = int64_t>

bool pgl::Rational< Int >::isInteger ( ) const

inlinenodiscardconstexpr

Whether this rational is exactly an integer.

A normalized fraction is whole exactly when its denominator is one. A deferred fraction may spell an integer with a larger denominator, so it is tested by divisibility without first computing or copying its reduced numerator and denominator.

isNegativeOne()

template<class Int = int64_t>

template<class I>

constexpr bool pgl::Rational< Int >::isNegativeOne ( const I & n )

inlinestaticconstexpr

Whether an integer argument is exactly -1.

Spelled out rather than written inline so that -1 is never formed in an unsigned type, where it would denote the maximum value and warn under -Wsign-compare. An unsigned argument simply never takes the branch.

lowerBound()

template<class Int = int64_t>

template<std::floating_point Float = double>

Float pgl::Rational< Int >::lowerBound ( ) const

inlineconstexpr

Computes a monotone, downward-rounded floating-point approximation of num / den.

This function f returns a float approximation r of the rational value num / den such that:

1. Lower bound property: r <= num / den i.e., the result never exceeds the exact mathematical value.
2. Monotonicity: If num'/den' >= num/den, then f(num',den') >= f(num,den) meaning the function preserves ordering between rational values.

Returns

A double r such that r <= num / den and the mapping is monotone.

Warning

This function may perform multiple calls to std::nextafter in rare cases where the initial floating-point approximation overshoots by more than one ULP. In practice, this is uncommon.

numerator()

template<class Int = int64_t>

Int pgl::Rational< Int >::numerator ( ) const

inlineconstexprnoexcept

Get numerator (in lowest terms).

operator double()

template<class Int = int64_t>

pgl::Rational< Int >::operator double ( ) const

inlineexplicitconstexpr

Convert to double.

An integral value – which is what a coordinate read out of integer input is, and what the sign filters convert over and over – takes the numerator's conversion alone. Dividing it by a converted 1 would give the same double, one conversion and one division later; over a wide Int neither is cheap.

operator float()

template<class Int = int64_t>

pgl::Rational< Int >::operator float ( ) const

inlineexplicitconstexpr

Convert to float.

operator Int()

template<class Int = int64_t>

pgl::Rational< Int >::operator Int ( ) const

inlineexplicitconstexpr

Convert (truncating toward zero) to the numerator integer type, for Int types not already covered by operator int/operator int64_t above, such as BigInt. den > 0 is an invariant, so the truncating division num / den matches truncating the exact value regardless of whether the fraction is stored reduced.

operator int()

template<class Int = int64_t>

pgl::Rational< Int >::operator int ( ) const

inlineexplicitconstexpr

Convert (truncating toward zero) to int.

The division happens in Int and only the quotient is narrowed. Doing it the other way round — narrowing num and den and dividing those — would be wrong for every fraction stored unreduced: normalization is deferred, so a value as ordinary as 5 can be carried as a ratio of two numbers far past int, and narrowing each of them independently turns the quotient into noise. The exact value fits or it does not; the parts it happens to be written with are not the caller's business.

operator int64_t()

template<class Int = int64_t>

pgl::Rational< Int >::operator int64_t ( ) const

inlineexplicitconstexpr

Convert (truncating toward zero) to int64_t. Divides first, for the reason given on operator int() const.

operator long double()

template<class Int = int64_t>

pgl::Rational< Int >::operator long double ( ) const

inlineexplicitconstexpr

Convert to long double.

operator Rational< OtherInt >()

template<class Int = int64_t>

template<class OtherInt>

pgl::Rational< Int >::operator Rational< OtherInt > ( ) const

inlineexplicitconstexpr

Convert to another Rational.

operator!=()

template<class Int = int64_t>

bool pgl::Rational< Int >::operator!= ( const Rational< Int > & r ) const

inlineconstexpr

operator*() [1/2]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

Rational pgl::Rational< Int >::operator* ( const I & x ) const

inlineconstexpr

operator*() [2/2]

template<class Int = int64_t>

Rational< Int > pgl::Rational< Int >::operator* ( const Rational< Int > & r ) const

inlineconstexpr

operator*=()

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator*= ( const Rational< Int > & r )

inlineconstexpr

operator+() [1/2]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

Rational pgl::Rational< Int >::operator+ ( const I & x ) const

inlineconstexpr

operator+() [2/2]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator+ ( const Rational< Int > & r ) const

inlineconstexpr

operator++() [1/2]

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator++ ( )

inlineconstexpr

operator++() [2/2]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator++ ( int )

inlineconstexpr

operator+=()

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator+= ( const Rational< Int > & r )

inlineconstexpr

operator-() [1/3]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator- ( ) const

inlineconstexpr

operator-() [2/3]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

Rational pgl::Rational< Int >::operator- ( const I & x ) const

inlineconstexpr

operator-() [3/3]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator- ( const Rational< Int > & r ) const

inlineconstexpr

operator--() [1/2]

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator-- ( )

inlineconstexpr

operator--() [2/2]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator-- ( int )

inlineconstexpr

operator-=()

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator-= ( const Rational< Int > & r )

inlineconstexpr

operator/() [1/2]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

Rational pgl::Rational< Int >::operator/ ( const I & x ) const

inlineconstexpr

operator/() [2/2]

template<class Int = int64_t>

Rational pgl::Rational< Int >::operator/ ( const Rational< Int > & r ) const

inlineconstexpr

operator/=()

template<class Int = int64_t>

Rational & pgl::Rational< Int >::operator/= ( const Rational< Int > & r )

inlineconstexpr

operator<=>() [1/4]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

std::strong_ordering pgl::Rational< Int >::operator<=> ( const I & n ) const

inlineconstexpr

Exact three-way comparison against an integer value.

The integer is never turned into a Rational to be compared against. Since den > 0, num/den <=> n is the sign of num - n*den, so the whole comparison stays in the integer domain; going through Rational(n) instead would copy the integer, multiply it by the denominator and multiply the numerator by one — for a BigInt, three heap-capable operations where none is needed.

The cases that dominate need no multiplication at all: against 0 the answer is the sign of the numerator, against ±1 it is the numerator against ±den, and a fraction that is already an integer compares directly. Predicates over rational coordinates are full of these — every orientationSign(...) == 0 collinearity test is a comparison against zero.

operator<=>() [2/4]

template<class Int = int64_t>

std::strong_ordering pgl::Rational< Int >::operator<=> ( const Rational< Int > & r ) const

inlineconstexpr

Three-way comparison operator.

operator<=>() [3/4]

template<class Int = int64_t>

template<class U>
requires (!std::same_as<U, Int>)

std::strong_ordering pgl::Rational< Int >::operator<=> ( const Rational< U > & r ) const

inlineconstexpr

Three-way comparison against a Rational of a different integer type.

Without this overload, comparing two distinct Rational instantiations is ambiguous under C++20: the same-type operator<=> would have to convert one operand up (non-reversed candidate) and the other down (reversed candidate), with neither winning. Providing an exact heterogeneous match resolves the comparison via the reversed-candidate tiebreaker.

operator<=>() [4/4]

template<class Int = int64_t>

template<std::floating_point Float>

std::partial_ordering pgl::Rational< Int >::operator<=> ( Float f ) const

inline

Exact three-way comparison against a floating-point value (partial: NaN compares unordered).

operator==() [1/4]

template<class Int = int64_t>

template<class I>
requires (pgl::detail::extended_integral<I> || std::same_as<I, Int>)

bool pgl::Rational< Int >::operator== ( const I & n ) const

inlineconstexpr

Exact equality against an integer value.

Shares every fast path of the three-way comparison above; the orderings it returns are settled by the same integer comparison an equality test would perform.

operator==() [2/4]

template<class Int = int64_t>

bool pgl::Rational< Int >::operator== ( const Rational< Int > & r ) const

inlineconstexpr

Equality comparison.

operator==() [3/4]

template<class Int = int64_t>

template<class U>
requires (!std::same_as<U, Int>)

bool pgl::Rational< Int >::operator== ( const Rational< U > & r ) const

inlineconstexpr

Equality comparison against a Rational of a different integer type.

Mirrors the heterogeneous operator<=> so mixed-type ==/!= are unambiguous. Both operands are reduced first, once each, so equal value is equal numerator and denominator.

operator==() [4/4]

template<class Int = int64_t>

template<std::floating_point Float>

bool pgl::Rational< Int >::operator== ( Float f ) const

inline

Exact equality against a floating-point value.

reciprocal()

template<class Int = int64_t>

Rational pgl::Rational< Int >::reciprocal ( ) const

inlineconstexpr

safeRaw()

template<class Int = int64_t>

bool pgl::Rational< Int >::safeRaw ( ) const

inlineconstexpr

Whether the raw num/den can be combined as-is without first reducing (i.e. already normalized, or small enough to be safe).

simplified()

template<class Int = int64_t>

Rational pgl::Rational< Int >::simplified ( ) const

inlinenodiscardconstexpr

Returns this value reduced to lowest terms.

The const counterpart of simplify: for a value that cannot be modified — one reached through a const reference, a container element, a function parameter — this hands back a copy the caller can store and read freely. It is also the cheap way to obtain both parts of a deferred fraction, since numerator() and denominator() each run their own gcd over the same pair, and this one runs it once.

Returns

An equal value whose stored parts satisfy gcd(|num|, den) == 1.

simplifiedIfLarge()

template<class Int = int64_t>

Rational pgl::Rational< Int >::simplifiedIfLarge ( ) const

inlinenodiscardconstexpr

Returns this value reduced, but only when it is already wide enough that the next arithmetic step would reduce it anyway.

The const counterpart of simplifyIfLarge, on the same width test, for a value that cannot be modified in place. Returns an equal value either way — reduced when the test fires, and an unchanged copy when it does not.

Returns

A value equal to this one, in lowest terms when it was wide.

simplify()

template<class Int = int64_t>

void pgl::Rational< Int >::simplify ( )

inlineconstexpr

Reduces the stored fraction to lowest terms in place (den stays > 0).

The reduction this type defers is normally recomputed and thrown away at every read: numerator and denominator each run their own gcd and keep nothing, so a value read k times pays for k reductions — and twice that when both parts are wanted. Calling this once, on a value that is about to be read repeatedly (hashed into a container, compared across a sweep, carried through a chain of predicates), collapses all of it to a single gcd; every later read then takes the already-normalized fast path.

Being non-const is the whole point: the result is stored, which is what a const read cannot do. Nothing about the value changes, so this is only ever a performance decision, never a semantic one.

See also

simplified() for the const version, which returns the reduced value instead of storing it.

simplifyIfLarge()

template<class Int = int64_t>

void pgl::Rational< Int >::simplifyIfLarge ( )

inlineconstexpr

Reduces in place, but only when the stored parts have already grown wide enough that the next arithmetic step would reduce them anyway.

The no-regression form of simplify. Arithmetic on a deferred fraction reduces its operands whenever they have grown wide — see operandParts — and throws that reduced form away with the expression's locals, so a wide value feeding many operations is reduced once per operation. This runs that same reduction a single time and keeps it, under exactly the same width test the arithmetic itself applies. A value below that width is left alone, because nothing downstream would have reduced it either.

So it never spends a gcd the library was not going to spend, which makes it safe to apply to a stored value whose use is not known in advance. What it will not do is reduce a narrow fraction to keep everything computed from it narrower; that is a bet on later use, and only simplify makes it. Where the values are known to be read many times over — the vertices an arrangement interns, say — that bet pays, and simplify is the right call even though it costs reductions this one would skip.

See also

simplifiedIfLarge() for the const version.

upperBound()

template<class Int = int64_t>

template<std::floating_point Float = double>

Float pgl::Rational< Int >::upperBound ( ) const

inlineconstexpr

Computes a monotone, upward-rounded floating-point approximation of num / den.

This function f returns a float approximation r of the rational value num / den such that:

1. Upper bound property: r >= num / den i.e., the result is never below the exact mathematical value.
2. Monotonicity: If num'/den' <= num/den, then f(num',den') <= f(num,den) meaning the function preserves ordering between rational values.

Returns

A double r such that r >= num / den and the mapping is monotone.

Warning

This function may perform multiple calls to std::nextafter in rare cases where the initial floating-point approximation overshoots by more than one ULP. In practice, this is uncommon.

Friends And Related Symbol Documentation

operator*

template<class Int = int64_t>

Rational operator* ( Int x, const Rational< Int > & r )

friend

operator+

template<class Int = int64_t>

Rational operator+ ( Int x, const Rational< Int > & r )

friend

operator-

template<class Int = int64_t>

Rational operator- ( Int x, const Rational< Int > & r )

friend

operator/

template<class Int = int64_t>

Rational operator/ ( Int x, const Rational< Int > & r )

friend

operator<<

template<class Int = int64_t>

std::ostream & operator<< ( std::ostream & os, const Rational< Int > & r )

friend

Output format: num/den or just num if den==1.

operator>>

template<class Int = int64_t>

std::istream & operator>> ( std::istream & is, Rational< Int > & r )

friend

Input format: num/den or integer.