A comparative study of algorithms for computing continued fractions of algebraic numbers (Q4375595)

The `basic method' of computing the continued fraction of a real number requires its approximate value as an input, and the well known truncate-and-invert step is then iterated to deliver the partial quotients and the accompanying complete quotients. Recently, \textit{E. Bombieri} and \textit{A. J. van der Poorten} [in Computational algebra and number theory, Sydney 1992, 137-152 (1995; Zbl 0835.11025)] and \textit{P. Shiu} [Math. Comput. 64, 1307-1317 (1995; Zbl 0834.11004)] gave what the latter called a `direct method' for the computation of the continued fraction when the number concerned is defined by certain functions. The new method is direct in the sense that the requirement of an input value is replaced by function evaluations at appropriate steps in the execution of the algorithm. The proposal by Bombieri and van der Poorten applies to algebraic numbers, and the reviewer's proposal may also be applied to deal with a certain class of transcendental numbers including \(\pi\), \(\log \pi\) and \(\log 2\). The authors now propose a `polynomial method' for algebraic numbers and give a comparative study of algorithms when applied to such numbers. The polynomial method requires only the coefficients of the defining polynomial in order to deliver the continued fraction. Instead of function evaluations, an updated set of coefficients are computed at appropriate steps. Explicit error controls are established, and full implementational details, together with experimental results for the first \(200 000\) partial quotients for six algebraic numbers, are also given. For the entire collection see [Zbl 0852.00023].