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.

How could we convert a rational number (less than $1$) to the continued fraction form?

This is probably an extension of this question. After reading Bill Dubuque's answer here and here, I got curious about continued fractions and tried myself to convert rationals into continued fractions. I noticed that for rational numbers greater than $1$ we could use extended Euclid theorem for gcd computation (manually), but I am not sure how to do the same for rationals less than $1$. Any ideas?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

The recursion for computing the continued fraction expansion $\rm\:\langle x \rangle\:$ of a real $\rm\:x > 0\ $ is as follows

$$\rm \langle x\rangle\ =\ \lfloor x\rfloor\ + \dfrac{1}{\langle (x-\lfloor x\rfloor)^{-1}\rangle}\:,\qquad where\ \ \ \lfloor x\rfloor\ :=\ floor(x)\ $$

For example

$$\rm \bigg\langle\frac{3}{8}\bigg\rangle\ \ =\ \ 0\: +\: \cfrac{1}{\bigg\langle\cfrac{8}3\bigg\rangle}\ \ =\ \ 0 \:+\: \cfrac{1}{2 + \cfrac{1}{\bigg\langle\cfrac{3}2\bigg\rangle}}\ \ =\ \ 0\: +\: \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}2}} $$

share|improve this answer

Find the c.f. of the reciprocal, then put that under $1$ in a fraction. For example $3/2=1+1/2$, so

$$\frac{2}{3}=0+\cfrac{1}{1+\cfrac{1}{2}}.$$

share|improve this answer

Using the Euclidean algorithm for $\frac{3}{8}$ we have, $$ \begin{align*} 3&=8(0)+3\\ 8&=3(2)+2\\ 3&=2(1)+1\\ 2&=1(2)+0 \end{align*} $$ and we take the quotients as our convergents $q_1=0$, $q_2=2$, $q_3=1$, and $q_4=2$. Sometimes it's useful to look at only the first few convergents. For hand computation I've been using the following (albit odd) method.

$ \begin{array}{cc|ccc} \,&\,&0&2&1&2\\ \hline 0&1&0&1&1&3\\ 1&0&1&2&3&8 \end{array} $

The top row lists the quotients. The 0 in row two is computed by $0(0)+1=0$. Then moving right, $2(0)+1=1$. Then, $1(1)+0=1$. Then, $2(1)+1=3$. The third row always starts with 1. Here, $0(0)+1=1$. Then, $2(1)+0=2$ and $1(2)+1=3$, finally $2(3)+2=8$.

In general, taking the top and bottom number under one of the quotients (or convergents) gives the fraction up to that point. That is, $\frac{1}{3}=0+\cfrac{1}{2+\cfrac{1}{1}}$ and using them all gives the orignal fraction $\frac{3}{8}$.

Finally, the last chunk of 4 numbers, "take the diagonal" note $1(8)-3(3)=-1$ and $3(3)-1(8)=1$. In general for a fraction one of those diagonals is the (positive) GCD.

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.