Rational Representation and Arithmetic

Overview

Rational represents arbitrary-precision rational numbers, holding two Int values (numerator $p$ and denominator $q$). The value satisfies:

$$x = \frac{p}{q}, \quad q > 0, \quad \gcd(|p|, q) = 1$$

Every operation reduces the result automatically with the binary GCD algorithm, maintaining the canonical form. Division by zero is handled safely via a NaN state.

For API usage, see Rational API Reference — Arithmetic Operators.

Internal Representation and Invariants

The class holds two Int members:

class Rational {
    Int num;   // numerator p (signed)
    Int den;   // denominator q (always positive, or 0 in NaN state)
    // ...
};

Invariants:

• $q > 0$ — the sign is consolidated in the numerator
• $\gcd(|p|, q) = 1$ — canonical (reduced) form
• $q = 0$ is the NaN state — including $p = 0, q = 0$

Because $q > 0$, sign decisions look only at the numerator, and comparisons avoid the inequality-flip case analysis that signed denominators would require.

Normalization happens at the end of every constructor and operator, so users always receive reduced values. If skipping reduction is desired for performance, use Rational(num, den, /*doReduce=*/false) and call reduce() later.

Automatic Reduction — Binary GCD

The core operation in reduction is GCD. To reduce $p/q$, compute $g = \gcd(|p|, q)$ and divide both by $g$.

sangi uses Stein's binary GCD algorithm. Its asymptotic complexity is the same as the Euclidean algorithm ($O(\log \min(a, b))$ iterations), but each iteration uses right shifts and subtractions instead of multiprecision modular reductions, which makes per-iteration cost dramatically smaller.

$$\gcd(a, b) = \begin{cases} a & (b = 0) \\ 2 \gcd(a/2, b/2) & (a, b \text{ both even}) \\ \gcd(a/2, b) & (a \text{ even}, b \text{ odd}) \\ \gcd(a, b/2) & (a \text{ odd}, b \text{ even}) \\ \gcd((a - b)/2, b) & (a, b \text{ both odd}, a \geq b) \end{cases}$$

For multiprecision Int values both right shift and subtraction run in linear time $O(n)$, which makes binary GCD fast in practice.

Addition and Subtraction — Bloat Suppression

Naive Formula and Bloat

The naive implementation is:

$$\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d}$$

For large $b$ and $d$, intermediate values $ad$, $bc$, $bd$ grow to size $bd$, and final reduction shrinks them. The dominant cost is the intermediate size.

Pull the Common Factor Out First

Compute $g = \gcd(b, d)$ first and write $b = g b'$, $d = g d'$:

$$\frac{a}{b} + \frac{c}{d} = \frac{a d' + c b'}{g \, b' \, d'} = \frac{a d' + c b'}{\operatorname{lcm}(b, d)}$$

The numerator stays at the scale $a d' + c b'$ and the denominator is $\operatorname{lcm}(b, d) = bd/g$. The final reduction only needs $\gcd(\text{new numerator}, g)$, which is cheap. Because multiprecision cost is governed by intermediate sizes, this is a real speedup.

Complexity

• One $\gcd(b, d)$: binary GCD in $O(M \log M)$ with $M = \max(\operatorname{size}(b), \operatorname{size}(d))$
• Two divisions $b/g$, $d/g$
• Three multiplications $a d'$, $c b'$, $b' d' g$
• One addition and one final reduction

Subtraction $a/b - c/d$ uses the same framework.

Multiplication

$$\frac{a}{b} \times \frac{c}{d} = \frac{a c}{b d}$$

The naive form computes $a c$ and $b d$ and then reduces. sangi instead cross-cancels in advance: compute $g_1 = \gcd(|a|, d)$ and $g_2 = \gcd(|c|, b)$, then:

$$\frac{a}{b} \times \frac{c}{d} = \frac{(a / g_1)(c / g_2)}{(b / g_2)(d / g_1)}$$

$a/g_1$ and $b/g_2$ are coprime, and similarly $c/g_2$ and $d/g_1$ are coprime, so the final step requires no further reduction (or only a trivial one):

$$\gcd\!\left(\frac{a}{g_1} \cdot \frac{c}{g_2}, \frac{b}{g_2} \cdot \frac{d}{g_1}\right) = 1$$

Cost: 2 GCDs + 4 divisions + 2 multiplications.

Division and Remainder

Division

$$\frac{a}{b} \div \frac{c}{d} = \frac{a}{b} \times \frac{d}{c} = \frac{a d}{b c}$$

The reciprocal is taken first and then multiplication is applied. If $c < 0$, the sign of $(ad)/(bc)$ ends up on the denominator, and the normalization phase moves it back to the numerator to restore the invariant $q > 0$.

Remainder

Rational remainder is not standard mathematically, but sangi defines it as:

$$r \bmod s = r - \lfloor r / s \rfloor \cdot s$$

The result is again a rational number. Because the integer part uses floor, the result always satisfies $0 \leq r \bmod s < |s|$ (signed according to $s$).

Comparison — Cross-Multiplication

Comparing $a/b$ and $c/d$ via real division would lose precision and run slowly. sangi reduces the comparison entirely to integer operations via cross-multiplication:

$$\frac{a}{b} < \frac{c}{d} \iff a d < b c \quad (b, d > 0)$$

The invariant $b, d > 0$ ensures the inequality direction is preserved. Implementation: two Int multiplications and one Int comparison.

The C++20 three-way comparison <=> returns std::partial_ordering. NaN makes the order partial:

• Any comparison involving NaN yields unordered
• NaN == NaN is false

Comparison with Int / int

Comparing $a/b$ with an integer $n$ reduces to $a$ vs $n b$, treating $n$ as a Rational with denominator 1. Both Int and int overloads use this path.

Sign, Absolute Value, Reciprocal

Reciprocation is one of the chief advantages of Rational: it returns an exact reciprocal in $O(1)$ time, simply by swapping numerator and denominator. Reciprocation of Int or Float requires a division; in Rational it is structurally free.

floor / ceil / round / trunc

Integer rounding of $r = p / q$ goes through Int division and returns an Int:

$$\begin{aligned} \lfloor r \rfloor &= \operatorname{div}_{\text{floor}}(p, q), \\ \lceil r \rceil &= -\lfloor -r \rfloor, \\ \operatorname{trunc}(r) &= \operatorname{div}_{\text{trunc}}(p, q) \quad (\text{toward zero}), \\ \operatorname{round}(r) &= \lfloor r + 1/2 \rfloor \quad (\text{half up}). \end{aligned}$$

When $q = 1$ (integer-valued), all of the above return the numerator itself. frac(r) = r - floor(r) returns a Rational satisfying $0 \leq \operatorname{frac}(r) < 1$.

NaN and Division by Zero

Passing a zero denominator puts Rational into a NaN state:

Rational nan = Rational(1, 0);   // NaN
assert(nan.isNaN());

NaN behaviour mirrors IEEE 754:

• Any operation involving NaN returns NaN
• NaN == NaN is false
• Any comparison involving NaN is unordered (std::partial_ordering::unordered)
• Use isNaN() to check explicitly

No exception is thrown and the program does not abort, so a computation chain proceeds safely. Check isNaN() only where the final result must be valid.

Design Decisions

Why Reduce After Every Operation

If intermediate results are left unreduced, numerator and denominator can grow rapidly, and subsequent operations balloon in cost — sometimes exponentially. Reducing every step keeps total cost low. It also simplifies hashing and equality (only $p_1 = p_2 \land q_1 = q_2$ needs to be checked).

For performance-critical regions where reduction must be deferred, doReduce = false at construction time and an explicit reduce() later are available.

The Invariant $q > 0$

Fixing the denominator positive lets sign and comparison logic operate on the numerator alone, without the inequality-flip case analysis that signed denominators would require. Constructors and the normalization phase of division move signs to the numerator as needed.

Multiprecision: GCD-First Rather Than Multiplication-First

In multiprecision arithmetic, GCD is cheaper than multiplication or division (binary GCD is a linear-time chain of right shifts and subtractions, while mul/div are super-linear). Therefore the strategy "kill common factors with GCD first" is a net win even when it adds GCD operations: the resulting multiplications operate on smaller inputs. Add/sub and mul both apply this technique in the middle of the operation rather than at the end.

References

• Stein, J. (1967). "Computational Problems Associated with Racah Algebra". Journal of Computational Physics, 1 (3), 397–405. (Binary GCD)
• Knuth, D. E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd ed. Addison-Wesley, 1997. §4.5.1 (rational arithmetic), §4.5.2 (GCD).