From: Raymond Manzoni Subject: Re: The continued fraction of algebraic numbers Date: Sat, 12 May 2001 23:37:08 +0200 Newsgroups: sci.math.research Summary: PSLQ (and other algorithms) to recognize algebraic numbers Hans Aberg wrote: > > It is known that the simple (reduced, with numerators 1) continued > fraction of a number x is finite exactly when x is rational, and > eventually periodic when x is quadratic. > > But what about the case when x is algebraic of a higher degree, is there > some kind of criterion like that the continued fraction coefficients > satisfies a recursion formula or something like that? > > Hans Aberg When the degree is higher than two a generalization of continued fractions is called "Higher-Order Continued Fractions" (see S. Finch [1] and Domingo Gomez Morin [2] ) : The idea is that one solution of sum_{k=1}^n c_k*x^k = 1 is (assuming convergence) : 1 --------------------- c_4+... c_3+ ------- c_1+... c_2+ ------------ c_2+... c_1+ ------- c_1+... c_1+----------------- c_3+... c_2+ ------- c_1+... c_1+ ------------ c_2+... c_1+ ------- c_1+... You'll note that the coefficients are given. If you purpose is to find these coefficients then a very powerful generalization of continued fractions is the PSLQ algorithm ([3],[4] I don't know if it considered as such but it is!). Another algorithm is the LLL algorithm and is widely implemented in Computer Algebra (for example in the free Pari/gp [5], Mathematica I think,...). The purpose of these algorithms is, for an incoming array of real [x_1, x_2, ..,x_n], to return the array of integers [i_1, i_2,.. ,i_n] verifying : i_1*x_1 + i_2*x_2 + ... + i_n*x_n = 0 (to the required precision) with Max_k |i_k| as small as possible. (for success the computation must be done with n*log10(Max_k|i_k|) digits at least) If you suppose that x is solution of a polynomial equation of degree less than n you only need to apply the previous algorithm to the input [1,x,...,x^(n-1)] to find your solution. I consider the PSLQ algorithm a generalization of continued fraction (not a very trivial one if you look at the algorithm! [3],[4]) since, for the input [1,x], the algorithm computes successively : round(x), round(1/(x-round(x))), and so on.. (simply replacing the classical floor function by the round function) Well, there is probably a simpler answer to your question, but I hope it helped anyway, Raymond [1] Steven Finch's essay "General Formula Involving Higher-Order Continued Fractions" http://pauillac.inria.fr/algo/bsolve/constant/pythag/dgm.html [2] Domingo Gómez Morín's "Generalized Continued Fractions" page at http://mipagina.cantv.net/arithmetic/GenContFrac.htm [edited:djr] [3] David H. Bailey and Simon Plouffe, Recognizing Numerical Constants http://www.cecm.sfu.ca/organics/papers/bailey [4] For an implementation of PSLQ in Mathematica : R.E. Crandall, "Topics in Advanced Scientific Computation", Springer/TELOS, New York http://www.telospub.com/catalog/MATHEMATICS/TASC.html [5] much faster is the 'lindep' function of the Pari/gp package : http://www.parigp-home.de/