An O(log n) algorithm for computing periodic continued fractions and its applications

AbstractAn O(log n) algorithm for computing the nth convergents of periodic continued fractions is presented. It can be applied to solve the second-order linear recurrences with constant coeffients very efficiently. We also use it to approximate the quadratic numbers in O(log m) time for a result with m-digit precision. Our method can be thought as a generalization of the matrix-vector approach for computing the Fibonacci numbers. It is easy to implement because there are only some matrix multiplications and a division operation involved