Continued Fractions

A continued fraction writes a number as a nested tower of fractions. It looks baroque, but it is the single best way to approximate a real number by simple fractions — and it falls straight out of the Euclidean algorithm.

The form

Every continued fraction is a stack of "integer part plus a reciprocal":

a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} = [a_0; a_1, a_2, a_3, \dots].

For a rational number this terminates and the partial quotients a_i are exactly the quotients in Euclid's algorithm. For \tfrac{43}{19}: 43 = 2\cdot 19 + 5, 19 = 3\cdot 5 + 4, … giving \tfrac{43}{19} = [2; 3, 1, 4].

The best approximations

Truncating a continued fraction gives its convergents — and these are, in a precise sense, the best possible rational approximations for their size of denominator. The convergents of \pi = [3; 7, 15, 1, 292, \dots] are

3, \quad \frac{22}{7}, \quad \frac{333}{106}, \quad \frac{355}{113}, \dots

The famous \tfrac{22}{7} and the astonishingly accurate \tfrac{355}{113} (correct to six decimals!) are simply early convergents. The huge next term 292 is exactly why \tfrac{355}{113} is so good.

Quadratic irrationals are periodic

Irrational numbers give infinite continued fractions — and for quadratic irrationals like \sqrt{n} they are eventually periodic, a theorem of Lagrange:

\sqrt{2} = [1; \overline{2}], \qquad \sqrt{7} = [2; \overline{1, 1, 1, 4}].

This periodicity is not a curiosity — it is the engine that solves Pell's equation, the next page.