Algorithms for computing continued fractions of algebraic numbers

166. R. P. Brent, A. J. van der Poorten and H. J. J. te Riele, A comparative study of algorithms for computing continued fractions of algebraic numbers (extended abstract), in Algorithmic Number Theory (Henri Cohen, editor), Lecture Notes in Computer Science, Vol. 1122, Springer-Verlag, Berlin, 1996, 35-47. MR 98c:11144.

Preliminary version: dvi (22K), pdf (194K), ps (70K).

Final version: pdf (224K), ps (78K).


The obvious way to compute the continued fraction of a real number x is to compute a very accurate numerical approximation of x, and then to iterate the well-known truncate-and-invert step which computes the next partial quotient q and the next complete quotient 1/(x-q). However, this is not necessarily the most efficient algorithm. In this paper we compare the efficiencies of algorithms which have been proposed in the literature by Bombieri and Van der Poorten, Shiu and others. In the course of the comparison we have computed about 200000 partial denominators of six different algebraic numbers.

A motivation for this study is the use of the continued fraction expansion of algebraic numbers in solution methods for certain Diophantine inequalities.

Go to next publication

Return to Richard Brent's index page