We begin with the classical method for finding the continued fraction
representation of a number . We put equal to the integer
part of , by which we mean the greatest integer less than or
equal to . If the fractional part of is not zero, we
put equal to the fractional part of . We then
invert , and put equal to the integer part of .
Similarly we put equal to the fractional part, and repeat.
Note that may be positive, negative, or zero, but that all the
subsequent will be positive, and that each is in the
interval .
This process gives us a unique continued fraction for each starting point
, and the process terminates if and only if is rational.
(For any rational there is one other simple continued fraction, e.g. ,
which is only trivially different from the one generated by this algorithm.)
This algorithm is related to the Euclidean algorithm
for finding the
greatest common divisor (gcd)
of two integers **k** and **m** [20],
in that if we use this method to find the continued fraction of , then
the integer parts that arise are precisely the quotients from the
Euclidean algorithm, and in fact the last nonzero remainder from the
Euclidean algorithm appears as the numerator of the last nonzero
fractional part. This remainder is of course the gcd of **k** and **m**.
Further, this algorithm can easily be seen to terminate in operations.