How to calculate the continued fraction of the square root of 13

(unfinished)

\sqrt{13} is some irrational number, with a weird decimal going on forever. With this method you can calculate it as exactly as you want, or the square root of any number, without having any idea what it is! Well, knowing only that it’s between 3 and 4. because 3^2=9 and 4^2 is 16, so it’s somewhere in there.

The only slightly tricky thing in this method is knowing (i.e. remembering from high school) how to get the \sqrt{} from the bottom to the top of a fraction, so read the short explanation of how to do that using conjugate surds if you need to.

OK, let’s begin…

We are going to make a continued fraction for \sqrt{13}, which may then be used to make rational approximations of any desired accuracy. (And convergents (fractions) made from continued fractions are the most accurate fractional approximations for their size.)

We will be finding x_0, x_1, x_2\dots , and the integers making up the continued fraction a_0,a_1,a_2\dots
Firstly, set x_0=\sqrt{13}.
The algorithm has only two steps, repeated ad nauseam:

Step 1. Set a_k=\lfloor x_k\rfloor
This is the ‘floor’ function, meaning round it down to the nearest integer. Which is lucky, cause that’s all I know about \sqrt{13}!
Step 2. \displaystyle x_{k+1}= \frac{1}{x_k-a_k}
Then repeat…

Ok, round 1.
1. a_0= \lfloor x_0 \rfloor = \lfloor \sqrt{13} \rfloor = 3.
2. \displaystyle x_1= \frac{1}{x_0-a_0} = \frac{1}{\sqrt{13}-3}

That was easy. Round 2*..
1. a_1=\lfloor x_1 \rfloor – and here’s the tricky bit I spoke of earlier, multiplying by the conjugate surd to make it much easier to deal with.
Hey, we’ve already done this step. \displaystyle x_1 = \frac{1}{\sqrt{13}-3} = \frac{\sqrt{13}+3}{4}
So \displaystyle \lfloor x_1 \rfloor = \lfloor \frac{3+3}{4} \rfloor. The \sqrt{13} is rounded down to 3 again.
And \;\displaystyle \frac{6}{4}=\frac{3}{2}\; is rounded down to 1. So a_1=1
2. \displaystyle x_2= \frac{1}{x_1-a_1} = \frac{1}{\frac{\sqrt{13}+3}{4}-1} = \frac{1}{\frac{\sqrt{13}-1}{4}}=\frac{4}{\sqrt{13}-1}

Round 3.
1. a_2=\lfloor x_2 \rfloor
First multiply by the conjugate as always. \displaystyle \frac{4(\sqrt{13}+1)}{(\sqrt{13}-1)(\sqrt{13}+1)}
2. \displaystyle x_3= \frac{1}{x_2-a_2}

Round 4.
1. a_3=\lfloor x_3 \rfloor
\displaystyle \frac{}{}
2. \displaystyle x_4= \frac{1}{x_3-a_3}

To be continued!

*Yes, this is a boxing metaphor. Weird, huh.

(Method stolen from Koshy’s Elementary Number Theory with Applications, 2007 – it’s just Euclid’s algorithm really.)

Leave a Reply

Your email address will not be published. Required fields are marked *