6
$\begingroup$

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?

  • 0
    Perhaps that [an example](http://math.stackexchange.com/questions/185971/how-do-i-solve-a-continued-fraction-of-solution-to-quadratic-equation) will help,2012-10-14
  • 0
    @RaymondManzoni It seems that the example doesn't explain the reason and I was having difficulty extending it to general algorithm...2012-10-14
  • 0
    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.2012-10-14
  • 0
    You might be interested in [the algorithm invented by Bill Gosper](http://perl.plover.com/classes/cftalk/INFO/gosper.txt); see the section titled "Square Roots of Continued Fractions".2012-10-14

1 Answers 1

4

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 :

$$\frac{\sqrt{S}-da+m}d=\frac{S-(da-m)^2}{d\bigl(\sqrt{S}+da-m\bigr)}$$

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 :

$$\frac{\sqrt{S}+da-m}{\frac{S-(da-m)^2}d}=\frac{\sqrt{S}+m'}{d'}$$

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$)

  • 0
    Thanks for your detailed explanation! Though I feel that your comment is more intuitive by having the subscript.2012-10-15
  • 0
    @chyx: I am Glad it helped. The ' notation is pleasant too (and a kind of tribute to the Great Dirac in his famous Book).2012-10-15