Exact Rational Arithmetic

Represent $\frac{p}{q}$ as a reduced pair of integers. Exact, comparable, and free of every floating-point question — at the cost of overflow risk.

Implementation

struct Frac {
    long long p, q;                                    // q > 0, gcd(|p|, q) == 1
 
    Frac(long long p = 0, long long q = 1) : p(p), q(q) { norm(); }
 
    void norm() {
        if (q < 0) { p = -p; q = -q; }
        long long g = __gcd(llabs(p), q);
        if (g) { p /= g; q /= g; }
        else q = 1;                                    // p == 0
    }
    Frac operator+(const Frac& o) const { return Frac(p*o.q + o.p*q, q*o.q); }
    Frac operator-(const Frac& o) const { return Frac(p*o.q - o.p*q, q*o.q); }
    Frac operator*(const Frac& o) const { return Frac(p*o.p, q*o.q); }
    Frac operator/(const Frac& o) const { return Frac(p*o.q, q*o.p); }
    bool operator<(const Frac& o)  const { return (__int128)p*o.q < (__int128)o.p*q; }
    bool operator==(const Frac& o) const { return p == o.p && q == o.q; }
};

Two details matter: normalise after every operation (otherwise denominators explode), and compare with __int128 cross-multiplication (otherwise comparison overflows long before the values do).

Overflow — the real constraint

Even reduced, denominators grow fast. Adding $n$ fractions with denominators up to $D$ can produce a denominator up to $D^n$ in the worst case. Practical limits:

Situation	Feasible
A handful of operations	yes
Sorting / comparing $n$ given fractions	yes — comparison alone does not grow anything
Summing hundreds of fractions	no — overflows
Gaussian elimination with fractions	overflows quickly; use Bareiss

Reduce before multiplying, not after — cross-cancel the gcds of the operands first:

Frac mul(Frac a, Frac b) {
    long long g1 = __gcd(llabs(a.p), b.q), g2 = __gcd(llabs(b.p), a.q);
    return Frac((a.p/g1) * (b.p/g2), (a.q/g2) * (b.q/g1));
}

Alternatives

Instead of fractions	Use
Rational answer mod a prime	$p\cdot q^{-1}\mathrm{mod}M$ — the modern contest convention
Comparing $\frac{a}{b}$ vs $\frac{c}{d}$	__int128 cross-multiplication, no struct needed
Money / bounded decimals	scale to integers (cents)
Exact linear algebra	Bareiss — fraction-free by construction
Geometry	keep intersection points as (num_x, num_y, den) triples
Probabilities	modular inverses

"Output $P\cdot Q^{-1}\mathrm{mod}998244353$"

Most modern problems asking for a rational answer phrase it this way, precisely so that no fraction arithmetic is needed: work in ${\mathbb{F}}_p$ throughout, and division is multiplication by a modular inverse. This is exact and has no overflow issues.

The Stern-Brocot tree

Every positive rational appears exactly once in an infinite binary search tree built from mediants:

$\mathrm{mediant}\left(\frac{a}{b},\frac{c}{d}\right)=\frac{a+c}{b+d}.$

Navigating it finds the simplest fraction in an interval, and the path from the root is the continued fraction expansion.

// simplest fraction strictly inside (lo, hi)
Frac simplest(Frac lo, Frac hi) {
    Frac l{0,1}, r{1,0};                               // 0/1 and "infinity"
    while (true) {
        Frac m{l.p + r.p, l.q + r.q};
        if (lo < m && m < hi) return m;
        if (m < lo) l = m; else r = m;
    }
}

Uses: best rational approximation with a bounded denominator, “simplest fraction in this range” problems, and the theory behind continued fractions.

Farey sequences

$F_n$ is the sorted list of reduced fractions in $[0,1]$ with denominator $\le n$. It has $1+{\sum }_{i=1}^n\phi (i)$ terms, and consecutive terms $\frac{a}{b}<\frac{c}{d}$ satisfy $bc-ad=1$ — which gives an $O(1)$ way to step to the next term:

// next Farey term after p/q, with the previous term a/b
long long k = (n + b) / q;
long long np = k * p - a, nq = k * q - b;

Useful for enumerating fractions in order without sorting, and for counting coprime pairs — see Euler Totient.

Continued fractions

$\frac{p}{q}=a_0+\frac{1}{a_1+\frac{1}{a_2+\dots }}$, with the $a_i$ being exactly the quotients of the Euclidean algorithm on $(p,q)$.

The convergents are the best rational approximations with bounded denominator, which is what Pell’s equation exploits.

See also: Floating Point · Modular Inverse · Pell’s Equation