Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to learn how to express a square root as continued fraction, but I can't get one thing.

The following example of $\sqrt{14}$ is from this page (click the image to see it at full size):

enter image description here

In the 2nd row of the table, can anyone please tell me where the 1 (in red) comes from? For instance, why can't it be 2, or 3, or 4?

This is my only doubt, which I've been trying hard to understand, but unable to.

share|improve this question
    
@Zev, thank you for your nice editing! :) –  xylon97 Feb 20 '13 at 16:39
1  
Glad to help! In general, it's best to capture things from external websites here so that if the link ever dies the question will still make sense :) –  Zev Chonoles Feb 20 '13 at 16:42

2 Answers 2

up vote 6 down vote accepted

Because $1$ is the greatest integer that is $\le \dfrac{\sqrt{14}+3}{5}$.

Remark: Recall the general continued fraction procedure. At any stage, we are looking at a number $x_n$, which is $\ge 1$ except possibly at the beginning. We compute $a_n=\lfloor x_n\rfloor$. If $a_n\ne x_n$, we define $x_{n+1}$ by $x_{n+1}=\dfrac{1}{x_n-a_n}$. Then $$x_n=a_n +\frac{1}{x_{n+1}}.$$ (There is a "better" algorithm for square roots of integers, and related numbers.)

share|improve this answer
    
Ah, thanks a lot. I don't think this has mentioned anywhere. Thanks again. –  xylon97 Feb 20 '13 at 16:43
1  
@hkapur97: You are welcome. It helps to carry out the algorithm on a calculator a few times. This is particularly easy if the calculator has a "$1/x$" button. Do it a few times. In particular, you might want to do it with the value of $\pi$ stored in your calculator. I am doing it now. So I called for $\pi$, got $3.14\dots$ on the display. Write down the greatest integer $\le \pi$, which is $3$. Subtract $3$, press the $1/x$ button. We get something a bit over $7$. Write down the $7$, subtract $7$ from the calculator result, press $1/x$. We get something very close to $16$, a bit under. –  André Nicolas Feb 20 '13 at 16:59
    
Write down $15$. Subtract $15$, flip. We get something a tiny bit over $1$. Write down a $1$. Continue. But soon it is unreliable, because calculator accuracy issues. However, look at the first approximation, namely $3$. The second is $3+\frac{1}{7}$, familiar! This way we get very good rational approximations to $\pi$ with smallish denominator. –  André Nicolas Feb 20 '13 at 17:03

More generally, if $x$ is real and $n$ is a natural number, then $$\left\lfloor \frac{x}{n}\right\rfloor = \left\lfloor \frac{\lfloor x\rfloor}{n}\right\rfloor$$

So in computing the continued fraction expansion of a square root of $D$, all the $x_i$ are of the form $$\frac{\sqrt D + A}{B}$$ and to find the integer part of this, we only need to find the integer part of:

$$\frac{\lfloor\sqrt D \rfloor+ A}{B}$$

That greatly simplifies the process of computing the integer parts at each step - the only "approximation" we need for $\sqrt{D}$ to compute this step is $\lfloor \sqrt{D}\rfloor$. Consider how much harder it would be if the $x_i$ could be of the form:

$$\frac{A_i\sqrt{D}+B_i}{C_i}$$

This essentially requirs a "better" estimate for $\sqrt{D}$ to find the integer part of this expression.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.