Fast computation of periodic continued fractions (Q750520)

The authors describe an O(log n) algorithm for computing the n-th convergent of a periodic continued fraction. Their algorithm is based on a scheme for substituting rational forms as symbolic terms in other rational forms. This allows a successive doubling of the number of cycles computed, where the first cycle is the periodic component of the continued fraction. The applications listed are to the computation of quadratic surds and to second order linear recurrences.