# Reference request for function by which to compute coefficients of continued fraction of algebaic number

The simple continued fraction is in the form $$[1;1,2,3,4,5,\dots]=1+\cfrac{1}{1+\cfrac{1}{2+\cdots}},$$ for instance. Obviously,the coefficients $x_i$can be computed by computable function $x_i=f(i), i\in \mathbb{N},$ and, $i$ is the $i$th coefficients.

Is there any function by which to compute coefficients of continued fraction of irrational algebraic non-quadritic number like $\sqrt{5}$? Any example is appreciated.

• There’s nothing wrong with your question, in my opinion, but it would be much more appropriate for Math Stack Exchange. Aug 23 '17 at 16:53
• @Lubin Do you think it does not reach the research level? I think if this question is solved, several question of number theory will be solved soon. Aug 23 '17 at 16:56
• This is not my field, but I believe that it has been the subject of research for well over a century. Aug 23 '17 at 17:03
• The simple continued fraction you give is not an algebraic number. By "coefficients" I take it you mean "partial quotients"? Alf van der Poorten had a paper about a way to get the partial quotients for (non-quadratic) algebraic irrationals, but I don't have the reference handy. Aug 23 '17 at 22:50
• If what question is solved? What questions of number theory would be solved soon based on this? The question in the post is too vaguely stated to make this at all clear. Aug 24 '17 at 1:48

This paper may be worth a look:

E. Bombieri and A. J. van der Poorten. Continued fractions of algebraic numbers. Computational algebra and number theory (Sydney, 1992), pp. 137–152. Kluwer Acad. Publ., 1995.

Also, R.P. Brent, Alfred J. van der Poorten, Herman J.J. te Riele: A comparative study of algorithms for computing continued fractions of algebraic numbers" Algorithmic Number Theory (Talence, 1996), pages 35-47, Lecture Notes in Computer Science, 1122, Springer, Berlin, 1996.

It's not very clear to me what the actual question is. If you know how to compute successive decimal approximations to a number like $\sqrt{5}$, then surely you know how to compute its continued fraction approximants based on that (subtract integer part, reciprocate, repeat). One can certainly write down an algorithm which does all that, and that surely qualifies as a "function" that computes the continued fraction expansion, and that would be an answer to the apparent question as stated.

However, this is undoubtedly an inelegant approach, and it is surely of interest to develop algorithms that are more direct than the cumbersome route of first computing decimal expansions and from there continued fractions. This is not a research area of mine, but my casual interest has made me a little bit aware of some work in this area.

For many years, Bill Gosper has been promulgating the virtues of continued fraction representations and has developed methods and computer algorithms for performing exact arithmetic on them. Let me quote him first (interview from More Mathematical People, p. 112):

Khinchin, in his book, talks about how wonderful continued fractions are but says, "Of course, there is no way to do arithmetic with them." When I sort of talked longingly of finding an algorithm to do arithmetic with continued fractions, Schroeppel just turned to me and said, "Good luck." I'm sure he feels a little bit guilty for that. When I showed him the algorithm that I found, his very first reaction was, "Oh, feedback." And then he said, "Oh, it won't work." It took me a while to realize that, in fact, it did work, that you really can write an algorithm [in this case, a Newton's method] and have the thing eat its own output as input and just take the square root of a continued fraction outright without any successive approximation at all. And that's true of anything amenable to Newton's method. It's completely astounding. It looks like you're cheating God somehow, and it really works.

The first part of this quote refers to algorithms Gosper developed for how to add, subtract, multiply, divide two given continued fractions, or more generally how to compute the c.f. of expressions $\frac{axy + bx + cy + d}{exy + fx + gy +h}$ ("bihomographic transformations") directly in terms of the c.f.'s of $x, y$. This is explained in a number of places, e.g. by Gosper in his famous HAKMEM 239, or in somewhat more pleasantly formatted form in a number of places such as Ben Lynn's notes here or a senior thesis here. Marc Dominus also has some nice lecture notes.

For the second part about Newton's method: it seems harder to find well-developed accounts. The idea is briefly touched upon in a generally enthusiastic report here (page 6), but Ben Lynn (in the notes referenced above, in his section on algebraic numbers) seems to believe that a more practical algorithm to compute the c.f. of say $\sqrt{5}$ is to write down the rational approximants of the root of $x^3 - 5$ based on Newton's method, which converge rather rapidly (quadratically), and convert those directly to continued fractions (which converge less rapidly -- linearly in fact).

Anyway, you might wish to explore the lore surrounding Gosper's algorithms.

• Thanks, but I hope the function is in closed form. Aug 24 '17 at 2:05
• Your answer gives a lots of reference, I highly appreciate Aug 24 '17 at 2:56