0
$\begingroup$

Let's say we want to find the continued fraction that solves the equation $x^2 - 2x - 1 = 0$.

Solution: $$ x = 2 + \frac1x = 2 + \dfrac1{2 + \dfrac1x} = 2 + \dfrac1{2 + \dfrac1{2 + \dfrac1x}} = [2;\overline2] $$

However, what happens if the quadratic is a bit more complicated, say, $2x^2 - 5x + 1 = 0$. If we use non-simple continued fractions to solve this, we get $$ x = \frac52 -\dfrac{\frac12}{\frac52-\dfrac{\frac12}{\frac52-\ddots}} \stackrel{how?}= [ 2; \overline{3, 1, 1} ] $$ My question is: How to convert non-simple continued fractions to simple continued fractions and in general how to solve quadratics using simple continued fractions?

$\endgroup$
  • $\begingroup$ Note that quadratics have (in general) two solutions, and whatever procedure you use to find a continued fraction, it will only give you one of the two solutions. $\endgroup$ – Gerry Myerson Jul 8 '18 at 4:02
1
$\begingroup$

$f(x)=2x^2-5x+1$.

$f(\alpha)=0$ for a number $\alpha$ with $2<\alpha<3$. So $a_0=2$, and $\alpha_1=1/(\alpha-a_0)$ is a zero of $f_1(x)=-x^2f(x^{-1}+2)=x^2-3x-2$.

Then $3<\alpha_1<4$, so $a_1=3$, and $f_2(x)=-x^2f_1(x^{-1}+3)=2x^2-3x-1$.

Then $a_2=1$, and $f_3(x)=-x^2f_2(x^{-1}+1)=2x^2-x-2$.

Then $a_3=1$, and $f_4(x)=-x^2f_3(x^{-1}+1)=x^2-3x-2=f_1(x)$, so from here on it repeats, giving $[2;\overline{3,1,1}]$.

This works not just for quadratics, but for any real algebraic number (although of course it's not periodic for nonquadratics).

Some references:

Cantor et al., A continued fraction algorithm for real algebraic numbers, Math Comp 26 (1972) 785-791.

Lang and Trotter, Continued fractions for soe algebraic numbers, J Reine Angew Math 255 (1972) 112-134; Addendum, 267 (1974) 219-220.

Richtmyer et al., Continued fraction expansions of algebraic numbers, Numer Math 4 (1962) 68-84.

Bombieri and van der Poorten, Continued fractions of algebraic numbers, in Computational Algebra and Number Theory, Sydney, 1992, Math Appl 325 (1995) 137-152.

Brent et al., A comparative study of algorithms for computing continued fractions of algebraic numbers, in Algorithmic Number Theory, Lecture Notes in Computer Science 1122 (Springer, 1996) 35-47.

$\endgroup$
  • $\begingroup$ Great answer! Do you know if there is an efficient way to convert non-simple (generalized) continued fractions to simple continued fractions. $\endgroup$ – Misha Shklyar Jul 8 '18 at 14:04
  • $\begingroup$ I was looking for that in the book, Neverending Fractions, by Borwein et al., but I couldn't find it there. Maybe I missed it, or maybe it's in one of Alf van der Poorten's many papers on continued fractions (or maybe it just isn't possible). $\endgroup$ – Gerry Myerson Jul 8 '18 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.