I was having difficulty understanding the algorithm to calculate Continued fraction expansion of square root.

I know the process is about extracting the integer part in repeat and maintaining the quadratic irrational $\frac{m_n + \sqrt{S}}{d_n}$. But I don't understand the equation:

$d_{n+1} = \frac{S - m_{n+1}^2}{d_n}$

Why $S - m_{n+1}^2$ is dividable by $d_n$?

This case for example:

$$\ \dfrac {1-\sqrt{5}}2=-1+\dfrac {3-\sqrt{5}}2$$

$$\frac 1{\dfrac {3-\sqrt{5}}2}=\frac 2{3-\sqrt{5}}=\frac {2(3+\sqrt{5})}{(3-\sqrt{5})(3+\sqrt{5})}=\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}=2+\frac {\sqrt{5}-1}{2}$$

If $S - m_{n+1}^2$ is not dividable by $d_n$, in the step $\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}$, it may result in some result like $\frac{3 + 3\sqrt{5}}{2}$ and break the algorithm. So why won't this happened?

  • $\begingroup$ Perhaps that an example will help, $\endgroup$ – Raymond Manzoni Oct 14 '12 at 16:06
  • $\begingroup$ @RaymondManzoni It seems that the example doesn't explain the reason and I was having difficulty extending it to general algorithm... $\endgroup$ – chyx Oct 14 '12 at 16:46
  • $\begingroup$ Fair point. This is not nice (I'm searching something clearer) but let's observe that we have $\ \displaystyle d_{n+1}=\frac{S-m_{n+1}^2}{d_n}\ $ with $\ \displaystyle m_{n+1}=d_na_n-m_n\ $ so that : $$\displaystyle d_{n+1}=\frac{S-(d_na_n-m_n)^2}{d_n}=\frac{S-m_n^2}{d_n}+2a_n m_n- d_n a_n^2$$ but we had previously (if $n>0$) $\ \displaystyle d_n=\frac{S-m_n^2}{d_{n-1}}\ $ so that $\displaystyle\frac{S-m_n^2}{d_n}=d_{n-1}$ and : $$ d_{n+1}=d_{n-1}+2a_n m_n-d_n a_n^2$$ (for $n=0$ $d_0=1$ is not a problem either) so that $d_{n+1}$ will always be an integer. $\endgroup$ – Raymond Manzoni Oct 14 '12 at 17:15
  • $\begingroup$ You might be interested in the algorithm invented by Bill Gosper; see the section titled "Square Roots of Continued Fractions". $\endgroup$ – MJD Oct 14 '12 at 17:45

At the start we have (for $m=0$ and $d=1$) : $$\sqrt{S}=\frac{\sqrt{S}+m}d=a+\frac{\sqrt{S}+m-da}d$$ (with $a,\ m$ and $d$ are integers)

Suppose that $\ d$ divides $(S-m^2)\ $ (this is true for $d=1$ of course).

The fractional part $\displaystyle \frac{\sqrt{S}+m-da}d$ becomes :


The numerator $\ S-(da-m)^2=(S-m^2)+da(2m-da)$ will be divisible by $d$ (from our hypothesis).
If we note $\ m':=da-m\ $ then the numerator divided by $d$ becomes $\ d':=\dfrac{S-(da-m)^2}d=\dfrac{S-m'^2}d$

and the next term to examine will be :


But the conditions are the same as at the start :

$\ d'$ divides $(S-m'^2)\ $ (the fraction is the previous $d$ !) and we may continue our rewriting : $$\frac{\sqrt{S}+m'}{d'}=a'+\frac{\sqrt{S}+m'-d'a'}{d'}$$

This recurrence shows that these conditions will hold at each iteration.
(To be complete let's add that at each step $\ a:=\left\lfloor\dfrac{\sqrt{S}+m}d\right\rfloor$)

  • $\begingroup$ Thanks for your detailed explanation! Though I feel that your comment is more intuitive by having the subscript. $\endgroup$ – chyx Oct 15 '12 at 3:26
  • $\begingroup$ @chyx: I am Glad it helped. The ' notation is pleasant too (and a kind of tribute to the Great Dirac in his famous Book). $\endgroup$ – Raymond Manzoni Oct 15 '12 at 6:43

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.