On efficient approximation of quadratic irrationals, signed Chebyshev polynomials and Householder's method

Abstract

We provide efficient algorithms to compute convergents of quadratic irrationals. We show that for square roots, in settings where Galois' refinement of Lagrange's theorem holds, certain decimations of the sequence of convergents are signed Chebyshev sequences, which can be also be generated by a Householder method.

12 pages, 11 references, no figures, V2 contains two additional (multiplicative) algorithms (3.4 and 3.5) and an additional example (3.4), V3 has new title, added info about convergents, and the costs of the algorithms are formulated as propositions