Continued fractions (3)

Each rational number can be represented as a finite continued fraction (FCF) and each FCF represents a rational number. We have seen how to calculate the rational number from a given FCF, in this post we show how to calculate the FCF for any rational number.

For example, the FCF representation of $\frac{17}{13}$ can be calculated as follows:

$a$	$q$	$b$	$r$
$17$	$1$	$13$	$4$
$13$	$3$	$4$	$1$
$4$	$4$	$1$	$0$

The value of the FCF is contained in the second column from top to bottom: $\frac{17}{13}$ is $\left[ 1,3,4 \right]$. This is clearly an application of Euclid's algorithm for calculating the GCD of two integers. The algorithm for calculating the GCD stops at row $3$ but by adding one more row containing $4 = 4 \times 1 + 0$ the column containing the FCF is complete.

See also:
- Continued fractions (1)
- Continued fractions (2)
- Continued fractions (2a)