Continued Fraction Calculator

A simple continued fraction expresses a number x as x = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + ...))), where a0 is any integer and a1, a2, a3, ... are positive integers called the partial quotients. The standard shorthand is [a0; a1, a2, a3, ...], with a semicolon after the integer part and commas separating the rest. For example, 22 / 7 = 3 + 1 / 7 is written [3; 7], and the golden ratio is [1; 1, 1, 1, 1, ...] because phi = 1 + 1 / (1 + 1 / (1 + 1 / (1 + ...))). Every rational number has a finite continued fraction (the algorithm terminates exactly when the remainder hits zero), and every irrational number has a unique infinite continued fraction. Continued fractions reveal arithmetic structure that decimal expansions hide: a periodic continued fraction means the number is a quadratic irrational (a root of an integer quadratic), and the partial quotients tell you how easily the number can be approximated by simple fractions.

The convergent h_n / k_n is the fraction you get when you truncate the continued fraction after n + 1 terms. There is a theorem from the theory of Diophantine approximation that says these convergents are best in a strong sense: no fraction with a denominator smaller than k_n comes closer to x than h_n / k_n does. So if you want the closest fraction to pi with a denominator up to 100, you compute the convergents of pi (1 / 1, 3 / 1, 22 / 7, 333 / 106, 355 / 113, ...) and pick the one with the largest denominator still under your cap, which is 22 / 7. The golden ratio is [1; 1, 1, 1, ...], whose convergents are F_{n+1} / F_n (consecutive Fibonacci numbers): 1 / 1, 2 / 1, 3 / 2, 5 / 3, 8 / 5, 13 / 8, .... Pi is [3; 7, 15, 1, 292, 1, 1, 1, ...]; its convergents 3, 22 / 7, 333 / 106, 355 / 113 are the famous historical approximations to pi. The big 292 means 355 / 113 is unusually accurate, agreeing with pi to seven decimal places.

The fraction-to-continued-fraction algorithm and the Euclidean algorithm for gcd are literally the same computation; you just keep different bookkeeping. Take 22 / 7. Divide: 22 = 3 * 7 + 1, quotient 3 (this is a0), remainder 1. Now invert and repeat with 7 / 1: 7 = 7 * 1 + 0, quotient 7 (this is a1), remainder 0. Stop. The terms are [3; 7], and the last non-zero remainder is gcd(22, 7) = 1. For 1071 / 462: quotients are 2, 3, 7, so the continued fraction is [2; 3, 7] and gcd(1071, 462) = 21 (the last non-zero remainder before the algorithm terminates). The reason this works is structural: each step computes a_i = floor(p / q), then replaces (p, q) with (q, p mod q). The quotients are the partial quotients of the continued fraction; the remainders are the intermediate gcd values. This calculator's fraction-to-cf mode is exactly the Euclidean algorithm, with the quotients reported instead of just discarded.

Because 22 / 7 is the fourth convergent of pi's continued fraction [3; 7, 15, 1, 292, ...] (the convergents are 3, 22 / 7, 333 / 106, 355 / 113, ...), and the first three are too crude to be useful. Convergent 3 / 1 is off by about 0.14; the second convergent 22 / 7 is off by only 0.00126, which is more than 100 times more accurate than any other fraction with a denominator at most 7. That accuracy gap is why Archimedes used 22 / 7 in the 3rd century BC and why it became the schoolbook approximation. The next convergent 333 / 106 is off by 8.3 x 10^-5, then 355 / 113 (a Chinese discovery by Zu Chongzhi around 480 AD) is off by 2.7 x 10^-7, agreeing with pi through the seventh decimal place. The reason 355 / 113 is so unusually good for its denominator size is that the next partial quotient of pi is 292, which is huge. A big a_n always means the previous convergent is exceptionally accurate, because the next term cancels little extra error.

A noble number is one whose continued fraction eventually consists entirely of 1s. The simplest example is the golden ratio phi = [1; 1, 1, 1, 1, ...], which is the noble number with the longest possible tail of 1s (every term is 1). The reason this matters is that the size of the partial quotients controls how well a number can be approximated by rationals: bigger a_n means the next convergent jumps closer to the value, so the number is easy to approximate. Conversely, small a_n means each convergent only inches a bit closer, so the number is hard to approximate by rationals with small denominators. Since the smallest legal partial quotient (after a0) is 1, a continued fraction of all 1s is the worst-case scenario for rational approximation. This is not just a curiosity. In dynamical systems and KAM theory, noble numbers (especially phi) are the most stable rotation numbers for invariant tori, because their poor approximability by rationals is exactly what keeps small resonant perturbations from destroying the orbit. So the same property that makes phi awkward for fraction-tables makes it the most physically robust irrational.