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.
Annotation Form Interface