Approximating 'big' ratio with 'small' ratio

Question

Given a ratio $ \frac{m}{n}, p \in N, q \in N $ where either $m$ or $n$ (or both) is a very big number, how can we find a ratio $ \frac{p}{q}, p \in N, q \in N $ which estimates $ \frac{m}{n} $ up to $ v $ significant digits and p and q are the smallest possible ones?

Example 1: $ m = 333333337, n = 1000000000 $, the best estimation for $ \forall v \in [1..7] $ is $ \frac{p}{q} = \frac{1}{3} $

Example 2: $ m = 42857, n = 100000 $, the best estimation for all $ \forall v $ is $ \frac{p}{q} = \frac{3}{7} $

I came up with the brute-force solution which is just to try all the combinations of $ p $ and $ q $ starting from 1 with the possible optimizations like finding the corresponding q by picking values $ q_1 $ and $ q_2 $ such that the desired $ q $ (if any) should satisfy $ q_1 \leq q \leq q_2 $. I estimated the worst case speed of such algorithm in $ O(10^v) $, provided $ m, n $ have the same order of magnitude and $ v < log_{10}m $

I'm interested in a solution, possibly suboptimal, which is much faster than mine. The 'real' values for $ m, n \approx 10^{50}; v \approx 30 $

Answer 1

http://en.wikipedia.org/wiki/Continued_fraction, perhaps?

At least 30 characters, sorry.

Answer 2

Assuming $m$ and $n$ are prime together

You can simplify the best approximation between the fractions $\frac{m'}{n'}$ with $m'=m-1,m,m+1$ and $n'=n-1,n,n+1$ and $m'$ not prime with $n'$

You can do it as long as it verifies the precision constraint.