How a continued fraction is computed

There is a simple algorithm for obtaining the continued fraction of any positive number, based on the repeated extraction of the integer part.

Observation — Algorithm for computing the continued fraction of a number

Given $\alpha>0$, write $\alpha = a_0 + \beta_0$ with $a_0=\lfloor\alpha\rfloor$ the integer part and $\beta_0\in[0,1)$. If $\beta_0\ne 0$, consider $1/\beta_0$ and repeat: $1/\beta_0 = a_1 + \beta_1$, and so on. For $\alpha\in\mathbb{Q}$ the process terminates; for $\alpha\notin\mathbb{Q}$ it goes on forever. The expansion is periodic if and only if $\alpha$ is a quadratic irrational (a root of a second-degree equation with rational coefficients), a result proved by Lagrange (cf. Stillwell, ch. 5).

Links

Topics: Second-degree equations
Concepts: Algorithm · Continued fraction · Quadratic irrational
Skills: Using formulas
People: Joseph-Louis Lagrange