Continued Fractions — Best Rational Approximation

Computing

a₀ = floor(x). Fractional part x' = 1/(x - a₀). Recurse. Terminates iff x rational.

Convergents

// p_0 = a_0, p_1 = a_0·a_1 + 1
// q_0 = 1, q_1 = a_1
// p_k = a_k·p_{k-1} + p_{k-2}
// q_k = a_k·q_{k-1} + q_{k-2}

Best approximation property

|x - p_k/q_k| < 1/(q_k · q_{k+1}). No smaller-denominator rational is closer.

Pell&amp;amp;#x27;s equation

x² - D·y² = 1. Solved via continued fraction expansion of √D.