I know there is a nice way of getting the continued fraction expansion of quadratic irrationals mainly because they recur after a point, and if they recur after a point they are quadratic irrationals. When constructing the expansion you can multiply by conjugates (kind of), e.g.

$\sqrt 3 =1+\sqrt 3 -1 = 1+\frac {1}{\frac {\sqrt 3 +1}{2}} $

Where you use $(\sqrt 3 - 1)(\sqrt 3 +1)=2$.

Are there identities that would help with the construction for $ \sqrt[3]{2} $?

One I thought was useful in the first step to get [1; 3,...] was

$ (\sqrt[3]{2}-1)( \sqrt[3]{4} + \sqrt[3]{2}+1 )=1$,

So you get:

$ \sqrt[3]{2}=1+( \sqrt[3]{2}-1 )=1+\frac {1}{ \sqrt[3]{4} + \sqrt[3]{2}+1 }= 1+\frac {1}{3+ (\sqrt[3]{4} + \sqrt[3]{2}-2)} $

Thanks for the help.

  • 3
    $\begingroup$ As far as I am aware very little is known about the continued fraction of any algebraic number with degree greater than $2$. However your computations can be simplified by working with polynomials, starting with the fact that $\root3\of2$ is a root of $x^3-2$. I have an exposition using this very example here starting at page 80. $\endgroup$
    – David
    May 3, 2014 at 13:21
  • $\begingroup$ @David Yeh, that was mentioned in our number theory class. Thanks for the link to the ps. It's really helpful (+1). Its pretty much an answer, that polynomial method and the identity that comes after it, for the more complicated way. Thanks for the post. $\endgroup$
    – snulty
    May 3, 2014 at 17:43
  • $\begingroup$ There are rules to derive CF for higher roots. For more info look at this Wikipedia page: en.wikipedia.org/wiki/Generalized_continued_fraction $\endgroup$ Sep 9, 2017 at 3:34
  • $\begingroup$ Not only the $3^{rd}$ but $n^{th}$ degree is actually explained in the Continued Fractions of Algebraic Numbers paper by Enrice Bombieri and Alfred J. var der Poorten paper at page 152. $\endgroup$
    – Redu
    Apr 2, 2022 at 18:58

3 Answers 3


Starting from the column vector $(1,0,0,-2)$, consider the following steps:

Step a) Repeat multiplication by the matrix $A$ $$A=\begin{bmatrix} 1&0&0&0\\ 3&1&0&0\\ 3&2&1&0\\ 1&1&1&1 \end{bmatrix}$$ while the coefficients of the resulting vector have different signs.

Step b) Reverse the coefficients of the vector, or equivalently multiply by $$B=\begin{bmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{bmatrix}$$

Then the number of times you multiply by $A$ in step a gives the partial quotients of continued fraction of $\sqrt[3]{2}$.

For, starting from $(1,0,0,-2)$, successive multiplication by $A$ gives: \begin{align} (1,0,0,-2) &\xrightarrow A\color{red}{(1,3,3,-1)}\\ &\xrightarrow A(1,6,12,6) \end{align} hence in step a we multiply by $A$ one time only, because $(1,6,12,6)$ have positive coefficients only, hence the first partial quotient is $1$: $$\sqrt[3]{2}=1+\cdots$$

Apply step b to $(1,3,3,-1)$ we get $(-1,3,3,1)$. Then applying step a to $(-1,3,3,1)$, successive multiplication by $A$ gives: \begin{align} (-1,3,3,1) &\xrightarrow A(-1,0,6,6)\\ &\xrightarrow A(-1,-3,3,11)\\ &\xrightarrow A\color{red}{(-1,-6,-6,10)}\\ &\xrightarrow A(-1,-9,-21,-3)\\ \end{align} hence the second partial quotient is $3$: $$\sqrt[3]{2}=1+\frac 1{3+}\cdots$$ and so on...

This algorithm holds for every algebraic number of third degree which is the only positive root of it minimal polynomial. For higher degree the matrix $A$ is enlarged as in the Tartaglia-Pascal triangle; for example for fourth degree: $$A=\begin{bmatrix} 1&0&0&0&0\\ 4&1&0&0&0\\ 6&3&1&0&0\\ 4&3&2&1&0\\ 1&1&1&1&1 \end{bmatrix}$$

For the intuition behind this algorithm. Then vector $(1,0,0,-2)$ corresponds to the polynomial $p(x)=x^3-2$. Multyplication by $A$ corresponds to $p(x)\mapsto p(x+1)$, while revesing in step b corresponds to $p(x)\mapsto x^3p(1/x)$. Finally Descartes's signs rule provide the stopping criterion in step a.

  • $\begingroup$ So just to see if I understand a bit why this works. $(1,0,0,-2)$ is representing $1x^3+0x^2+0x-2$. Then $A$ and $B$ are some kind of linear maps on this polynomial ring/vector space. $A$ looks like $p\mapsto p+p’+p’’/2!+p’’’/3!$, which is a kind of Taylor expansion, while B I suppose can be seen like the map $p(x)->x^3*p(1/x)$. I have no idea why this works though. Is there some intuition for it? It seems really cool. $\endgroup$
    – snulty
    Oct 26, 2019 at 10:37
  • $\begingroup$ @snulty: I added explanation in answer, thank'you $\endgroup$ Oct 26, 2019 at 11:09
  • $\begingroup$ @FabioLucchini Can this method be used to bound the continued fraction coefficients of $\sqrt[3]{2}$? $\endgroup$ Nov 10, 2019 at 18:49
  • $\begingroup$ @franklin I am not sure the ciefficients are bounded in the first place. $\endgroup$ Nov 10, 2019 at 21:57
  • $\begingroup$ @OscarLanzi No, they’re probably not bounded, but I meant bounding them using something like big-O notation (showing that they have sub-quadratic growth, or sub cubic growth, or sub-exponential growth, or something like that). $\endgroup$ Nov 10, 2019 at 22:28

The accepted answer looks like based on Vincent's continued fractions method (1836). Downside is it's inefficiency. Say, the root is at $0.000001$ so $a_0=0$. In order to calculate the next term $a_1$ you have to invert the polynomial and the root of the inverted polynomial appears at $1000000$. This means at the next stage you have to perform $p(x)↦p(x+1)$ translation 1000000 times.

Instead one should find the lowest bound $b_0$ of the positive roots and perform a $p_0(x)↦p_0(x+b_0+1) = p_1(x)$ translation. We should also know that the lowest bound is just a bound and most probably doesn't yield an exact figure that pinpoints the smallest positive root. This means, we may have to perform subsequent lowest bound attempts on the translated polynomials up until there is no sign change remains in the coefficients of the last obtained polynomial, a.k.a. $var(p_n(x)) = 0$ which means there is no positive root according to Descartes Rule of Sign Change. Then the $i^{th}$continued fraction coefficient $a_i$ would be the sum of all horizontal translation amounts less $1$ such as $a_i = b_{0,i}+b_{1,i}+...+b_{n,i}+n$. Obviously if the subsequent translations yield a no sign change at the polynomial coefficients and at the same time $p(0) = 0$ case occurs then the continued fraction ends here. If not then we need to perform $p(\frac{1}{x-1})$ translation (one step to the right and invert) which is two translations one after the other like $p(x-1)$ and $p(\frac{1}{x})$. Keep in mind that inverting a polynomial like $p(\frac{1}{x})$ is as simple as reversing the coefficients of the polynomial. Such as if $p(x) = x^4+7x^2+2x-5$ then $p(\frac{1}{x}) = -5x^4+2x^3+7x+1$ but we are only interested in the roots and should make the initial coefficient 1. Accordingly dividing all coefficients by $-5$ we can safely say that the $p(\frac{1}{x})$ of our interest would actually be $p(\frac{1}{x}) = x^4-\frac{2}{5}x^3-\frac{7}{5}x-\frac{1}{5}$.

Now there are two crucial parts to this problem.

  1. Efficiently and most precisely finding the lowest bound.
  2. Translating the polynomial by an arbitrary amount ($b_{lower}+1$) in it's extended form.

1. Lowest Positive Bound

There are several linear and quadratic algorithms to find the lower positive bound. Linear ones resolve faster but yielding a coarse lower bound while quadratic ones yield much finer bounds. Keep in mind that a sharper lower positive bound would minimize the translation count dramatically. According to my calculations on overall performance, I prefer a quadratic one. If you need to know more about them please drop a comment and i will extend the answer.

2. Translation of a Polynomial by an Arbitrary Amount

This is as simple as performing subsequent synthetic divisions, the degree of the polynomial many times. It's known as the Ruffini-Horner Method. A description of how it works can be found in one of my SO answers.

  • $\begingroup$ You might want to check out the Uspensky method, its variations by Zimmerman et al. and the corpus of articles by A. Akritas claiming that such a method does not exist. Especially the importance of employing advanced lower root bounds is also central there. $\endgroup$ May 27, 2022 at 8:58
  • $\begingroup$ @LutzLehmann Very recently I have come up with my own lower bound algorithm which works in linear time and much faster and even sharper than quadratics. Sometimes even pinpoints the root. However it only works with the polynomials originated from this very task which is sufficient. As in expressing the $41^{st}$ root of a rational $\frac{1453}{857}$ with the polynomial $f(x) = 857x^{41} -1453$. You can test it here. Orders allowed 1-100 and the rational can have $1\to2^{53}-1$ at the numerator and denominator. $\endgroup$
    – Redu
    Jul 18, 2022 at 19:19

Allowing generalized continued fractions, using the General Method for Extracting Roots using (Folded) Continued Fractions by Manny Sardina:

$$\sqrt[3]{1^3 + 1} = 1 + \delta$$ for $0 < \delta < 1$.

$$1^3 + 1 = (1 + \delta)^3 = 1 + 3\delta + 3 \delta^2 + \delta^3$$

$$\iff 1 = \delta(3 + 3\delta + \delta^2) $$

$$\iff \delta = \frac1 {3 + 3\delta + \delta^2}$$

The first approximation is $$\delta_1 = \frac1 {3 + 3 \delta_0 + \delta_0^2}$$

$\delta_0$ is small and the first estimate of $\delta_1 = 1/3$, so the first cube root estimate is $r_2 = 1 + \delta_1 = 4/3$.

The second approximation is

$$\delta_2 = \cfrac1{3 + 3 \left(\cfrac1{3 + 3\delta_0 + \delta_0^2} \right) + \left(\cfrac1{3 + 3\delta_0 + \delta_0^2} \right)^2}$$

$\delta_0$ is ignored, giving $$\delta_2 = \frac1{3 + 3(1/3) + (1/3)^2 } \approx \frac1{3+1}$$

The third approximation is $$\delta_3 = \cfrac1{3 + \cfrac1{1 + \cfrac 2 9}}$$

The full generalized continued fraction is $$\sqrt[3]2 = 1+\cfrac{1} {3+\cfrac{2} {2+\cfrac{4} {9+\cfrac{5} {2+\cfrac{7} {15+\cfrac{8} {2+ \ddots}}}}}}$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .