Aproximating rational with fraction with “smallest numerator and denumerator possible”

For example $0.795=\frac{159}{200}$. But is there a way to find fraction with smaller numerator and denumerator that will represent number $0.795xyz...$ i.e. it will approximate our given number?

I need algorithm or some procedure for this.

-

The smallest denominator $q$ is $q=44$ corresponding to $$\frac pq=\frac{35}{44}=0.795\overline{45}$$ To see this, note that $$\frac ab=\frac{31}{39}=0.79487\ldots$$ is too small and $$\frac cd=\frac{4}{5}=0.8$$ is too big. For any fraction with $\frac ab<\frac pq<\frac cd$, we have $$\frac pq-\frac ab=\frac{bp-aq}{bq}>0\qquad\frac cd-\frac pq=\frac{cq-dp}{dq}>0,$$ hence $$bp-aq\ge 1\qquad cq-dp\ge 1$$ and finally (because $bc-ad=1$) $$q=(bc-ad)q=d(bp-aq)+b(cq-dp)\ge b+d=44.$$

-

This is solved with continued fractions. Your specific example $0.795$ is the continued fraction $[0;1,3,1,7,5]$. It has convergents (best approximations) $0,1,\frac{3}{4},\frac{4}{5},\frac{31}{39},\frac{159}{200}$.

$\frac{4}{5}=0.8$ is pretty good, and $\frac{31}{39}=0.7948718\ldots$ is even better.

-
but what if I want this 0.795... not 0.794? I need first 3 decimal places to be exact. –  Meow May 19 '13 at 14:43
@Mare, $31/39$ is $0.795$ to three decimal places, because $0.7948$ rounds to $0.795$. –  vadim123 May 19 '13 at 14:46
Then modify the rounding. If you use $[0;1,3,1,8]$, you'll get $\frac{35}{44}$, which is 0.79545454... - it's a little further from exact, but still quite good. –  Glen O May 19 '13 at 14:48
@GlenO: that's what I was looking for =) –  Meow May 19 '13 at 14:53