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
    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
    @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