Rational Continued Fractions and Best Rational Approximation

Overview

The continued-fraction expansion of a rational $p/q$ is:

$$\frac{p}{q} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} = [a_0; a_1, a_2, a_3, \ldots]$$

with $a_0 \in \mathbb{Z}$ and $a_k \in \mathbb{Z}_{>0}$ for $k \geq 1$. For rationals the expansion is finite; irrationals expand into an infinite sequence.

sangi's Rational exposes toContinuedFraction() and fromContinuedFraction(). These enable best rational approximation under denominator bounds and various Float ↔ Rational conversions.

For API usage, see Rational API Reference — Continued Fraction.

Continued-Fraction Expansion — Euclidean Procedure

Algorithm

The coefficients $a_k$ are obtained by an iteration that is structurally identical to the Euclidean algorithm:

$$\begin{aligned} (r_0, r_1) &\leftarrow (p, q), \\ a_k &= \lfloor r_k / r_{k+1} \rfloor, \\ r_{k+2} &= r_k - a_k \, r_{k+1} = r_k \bmod r_{k+1}, \\ &\text{stop when } r_{k+2} = 0. \end{aligned}$$

This is exactly the iteration used to compute $\gcd(p, q)$; recording all quotients $a_k$ yields the continued-fraction coefficients.

Complexity: $O(\log \min(|p|, q))$ divisions. By Lamé's theorem, the length of the coefficient sequence is bounded by $O(\log_\phi q)$ where $\phi = (1+\sqrt{5})/2$.

Example

The continued-fraction expansion of $355/113$:

$$\begin{aligned} 355 &= 3 \cdot 113 + 16, & a_0 &= 3, \\ 113 &= 7 \cdot 16 + 1, & a_1 &= 7, \\ 16 &= 16 \cdot 1 + 0, & a_2 &= 16. \end{aligned}$$

So $355/113 = [3; 7, 16]$.

Reconstruction

To rebuild a rational from coefficients $[a_0; a_1, \ldots, a_n]$, fold from the tail:

$$x = a_n, \quad x \leftarrow a_k + 1/x \quad (k = n-1, n-2, \ldots, 0)$$

This is faster than generating convergents forward with the recurrence below and uses only integer arithmetic.

Convergent Recurrence

Truncating $[a_0; a_1, \ldots, a_n]$ at index $k$ gives the $k$-th convergent:

$$\frac{p_k}{q_k} = [a_0; a_1, \ldots, a_k]$$

Convergents are generated by the recurrence:

$$\begin{aligned} p_{-1} &= 1, & p_0 &= a_0, & p_k &= a_k p_{k-1} + p_{k-2}, \\ q_{-1} &= 0, & q_0 &= 1, & q_k &= a_k q_{k-1} + q_{k-2}. \end{aligned}$$

Written as a product of $2 \times 2$ matrices:

$$\begin{pmatrix} p_k & p_{k-1} \\ q_k & q_{k-1} \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_k & 1 \\ 1 & 0 \end{pmatrix}$$

Each factor has determinant $-1$, so the product has determinant $(-1)^{k+1}$, giving the identity:

$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k+1}$$

This shows that $p_k$ and $q_k$ are always coprime: convergents are reduced from the outset.

Example: Convergents of π

The continued-fraction expansion of $\pi = 3.14159265\ldots$ is $[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, \ldots]$. The first convergents are:

The large coefficient $a_4 = 292$ makes $355/113$ exceptionally good among rationals with denominator $\leq 113$: the next convergent costs a 100× larger denominator for only three more correct digits.

Connection to the Stern-Brocot Tree

The Stern-Brocot tree is a binary tree that generates every positive reduced rational exactly once by repeatedly inserting mediants between the current pair of neighbours:

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

The continued-fraction coefficients $[a_0; a_1, a_2, \ldots]$ correspond to a path in the tree:

• Start at the root $1/1$
• $a_0$ steps R (right)
• $a_1$ steps L (left)
• $a_2$ steps R (right)
• $\ldots$ alternating

Each convergent $p_k/q_k$ sits at the $k$-th turning point (direction change). The continued-fraction expansion is essentially a run-length encoding of the Stern-Brocot path.

sangi's nextMinimal() (next positive rational in Stern-Brocot order) and nextCalkinWilf() (next in Calkin-Wilf order) walk this tree directly.

Best Rational Approximation

Definition

For a real $x$ and denominator bound $D$, the rational $p/q$ with $q \leq D$ that minimizes $|x - p/q|$ is called a best rational approximation.

Lagrange's Theorem

The convergents $p_k/q_k$ of $x$'s continued-fraction expansion are best approximations, satisfying:

$$\left| x - \frac{p_k}{q_k} \right| < \frac{1}{q_k q_{k+1}} < \frac{1}{q_k^2}$$

and for every $p/q \neq p_k/q_k$ with $q \leq q_k$:

$$\left| x - \frac{p_k}{q_k} \right| < \left| x - \frac{p}{q} \right|$$

This is the essence of continued fractions and explains why $22/7$ and $355/113$ are "good" approximations of $\pi$.

Algorithm: Best Approximation with Denominator ≤ D

Compute the continued-fraction coefficients of the real $x$ incrementally and stop just before the convergent's denominator exceeds $D$. For finer control, try semiconvergents (replace $a_k$ with smaller $a'_k$ near the cutoff); the best approximation among those with $q \leq D$ may be a semiconvergent rather than a convergent.

Float ↔ Rational Conversion

Float → Rational (Exact Conversion)

Rational(double value) and Rational(const Float&) construct an exact representation $m \cdot 2^e$ from the IEEE 754 mantissa $m$ and exponent $e$. A "simple" decimal like $0.1$ is actually 3602879701896397 / 2^55 in IEEE 754, and exact conversion preserves this value verbatim.

Float → Rational (Continued-Fraction Approximation)

Exact conversion targets faithful reproduction of the binary representation, but recovering "the simple fraction a human meant" requires continued-fraction approximation. Restricting the denominator to at most $D$ recovers natural intent: $0.1 \to 1/10$, $0.3333\ldots \to 1/3$.

Typical use cases:

• Test fixtures: write expected values as double and convert to Rational for stable hashing IDs
• UI-entered decimals stored as exact rationals for downstream symbolic computation in CAS
• ML model weights represented as reduced fractions for reproducibility

Rational → Float

The reverse conversion toDouble(), toFloat(), toMpFloat(prec) casts numerator and denominator to Float and divides. When the digit counts of $p$ and $q$ greatly exceed the working precision (16 digits for double), IEEE 754 round-to-nearest is applied.

Hurwitz's Theorem

Hurwitz's theorem sharpens the best-approximation property of continued fractions:

Hurwitz (1891): for every irrational $\alpha$, infinitely many rationals $p/q$ satisfy:

$$\left| \alpha - \frac{p}{q} \right| < \frac{1}{\sqrt{5} \, q^2}$$

The constant $\sqrt{5}$ is best possible: no smaller constant works for every irrational. Equality (in a limit sense) is attained by numbers related to the golden ratio $\phi = (1+\sqrt{5})/2$, whose continued-fraction expansion is $[1; 1, 1, 1, \ldots]$.

Because $\phi$'s coefficients are all $1$, $\phi$ is "the hardest irrational to approximate". This property is the starting point of Diophantine approximation.

Design Decisions

Coefficient Type

toContinuedFraction() returns a std::vector<Int>. Coefficients can exceed int range in some cases (especially through Float-approximation routes), and using Int avoids both type conversion and overflow.

Finite versus Infinite

Rationals have finite continued fractions. Irrationals expand infinitely, so toContinuedFraction() is specific to Rational (with the finiteness guarantee). Irrational continued fractions belong to a separate API (a future Float-side lazy continued fraction).

Tail-Coefficient Normalization

When $a_n = 1$ and $n \geq 1$, the continued fraction $[a_0; a_1, \ldots, a_n]$ represents the same rational as $[a_0; a_1, \ldots, a_{n-1} + 1]$. sangi normalizes to either $a_n \neq 1$ or length 1, giving a unique representation and simplifying hashing and comparison.

References

• Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008. Chapter X (continued fractions).
• Khinchin, A. Ya. Continued Fractions. Dover, 1997.
• Graham, R. L., Knuth, D. E., and Patashnik, O. Concrete Mathematics. 2nd ed. Addison-Wesley, 1994. §4.5 (Stern-Brocot tree).