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).
Abstract
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