Continued fraction of a square root

If I want to find the continued fraction of $\sqrt{n}$ how do I know which number to use for $a_0$? Is there a way to do it without using a calculator or anything like that? What's the general algorithm for computing it? I tried to read the wiki article but was overwhelmed and lost. I tried Googling but couldn't find a website that actually explained this question.

If anyone has a good site that answers these questions either, please let me know. Thanks!

-

Let's just do an example. Let's find the continued fraction for $\def\sf{\sqrt 5}\sf$. $\sf\approx 2.23$ or something, and $a_0$ is the integer part of this, which is 2.

Then we subtract $a_0$ from $\sf$ and take the reciprocal. That is, we calculate ${1\over \sf-2}$. If you're using a calculator, this comes out to 4.23 or so. Then $a_1$ is the integer part of this, which is 4. So: $$\sf=2+\cfrac{1}{4+\cfrac1{\vdots}}$$

Where we haven't figured out the $\vdots$ part yet. To get that, we take our $4.23$, subtract $a_1$, and take the reciprocal; that is, we calculate ${1\over 4.23 - 4} \approx 4.23$. This is just the same as we had before, so $a_2$ is 4 again, and continuing in the same way, $a_3 = a_4 = \ldots = 4$: $$\sf=2+\cfrac{1}{4+\cfrac1{4+\cfrac1{4+\cfrac1\vdots}}}$$

This procedure will work for any number whatever, but for $\sf$ we can use a little algebraic cleverness to see that the fours really do repeat. When we get to the ${1\over \sf-2}$ stage, we apply algebra to convert this to ${1\over \sf-2}\cdot{\sf+2\over\sf+2} = \sf+2$. So we could say that: \begin{align} \sf & = 2 + \cfrac 1{2+\sf}\\ 2 + \sf & = 4 + \cfrac 1{2+\sf}. \end{align}

If we substitute the right-hand side of the last equation expression into itself in place of $2+ \sf$, we get:

\begin{align} 2+ \sf & = 4 + \cfrac 1{4 + \cfrac 1{2+\sf}} \\ & = 4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{2+\sf}}} \\ & = 4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{2+\sf}}}} \\ & = \cdots \end{align}

and it's evident that the fours will repeat forever.

-
I always thought they were in the form a0 + 1/(a1 + 1/ (a2 + 1/( ... – user51819 Dec 27 '12 at 2:01
@user51819 Quite so (although $a_0$ could be 0.) I had the typesetting wrong, and have corrected it. – MJD Dec 27 '12 at 2:03
Sorry, one last question; how do we know, in the general sense, when we've hit the point where it's periodic? When you encounter an $a_k$ you've seen before? Or when a reciprocal equals a reciprocal you've seen before? I am guessing the latter? – user51819 Dec 27 '12 at 2:09
When the reciprocal is one you have seen before. It couldn't be when you reach an $a_k$ you've seen before or else you couldn't have a repeating sequence like $1,1,2,1,1,2,1,1,2,\ldots$. – MJD Dec 27 '12 at 2:15
Incredible, really. – Meitar Jun 13 at 12:19

$a_0$ is simply the largest integer such that $a^2 \le n$ . You can determine the continued fraction for a square root by performing the $\frac1{\sqrt n - a_0}$ step and then using the conjugate to remove the square root from the denominator, and repeating.

I recommend Ron Knott's site: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html . Good Luck.

-

Confirm the algebraic identity: $$\sqrt n=a+\frac{n-a^2}{a+\sqrt n}$$ Then chose whatever value of 'a' you want, and just keep on pluging in $\sqrt n$

-

$a_0$ is the largest integer that is smaller than or equal to $\sqrt n$. Or put another way, you want $a_0^2$ to be smaller than or equal to $n$, and $(a_0+1)^2$ to be bigger than $n$.

If you really have no idea what integer to use, then you find it by guessing an integer $g$. Then you calculate $g^2$. If $g^2$ is bigger than $n$, your guess $g$ was too big, and you try a smaller guess. If $g^2$ is much smaller than $n$, your guess $g$ was too small, and you try a bigger guess. You keep doing this until you find a guess $g$ where $g^2 \le n$ and $(g+1)^2 > n$, and then $a_0 = g$.

-