Computers & Mathematics with Applications, Vol. 21 (1991), pp. 167-169.
Ömer Egecioglu, Cetin K. Koc, and Josep Rifa i Coma
Fast Computation of Continued Fractions
Abstract.
We give an O(log n) algorithm to compute the n-th convergent of a
periodic continued fraction. The algorithm is based on matrix representation
of continued fractions, due to Milne-Thomson. This approach also allows
for the computation of first n convergents of a general continued
fraction in O(log n) time using O(n/log n}) processors.
omer@cs.ucsb.edu