Approximate a float using a minimal fraction

This sounds like it's probably a well-known problem, but I haven't been able to find references to it by searching.

Given a floating point value $x$ and an error range $\varepsilon$, how can I efficiently find a minimal positive integer $q$ such that $\left|x - \frac{p}{q}\right| < \varepsilon$ for some integer $p$?

The approach that seems obvious is to iterate from $q = 1$ upward (skipping composite numbers), computing $p := round(x * q)$ and checking whether $\left|x - \frac{p}{q}\right| < \varepsilon$. But I'm wondering if there's a smarter way.

• 1. What are you trying to minimize? Please specify a single objective function to minimize. Is your goal to minimize $q$? 2. Have you looked at continued fractions? – D.W. Mar 23 '16 at 12:05
• @D.W.: I'm trying to minimize q. Sorry I wasn't more explicit... I thought that was equivalent to saying "minimal $p, q$", but maybe that's ambiguous when $x < 0$. I have edited the question to clarify. – LarsH Mar 23 '16 at 13:14
• @D.W.: I haven't looked at continued fractions for this problem. I don't think they would help... For a given $x$, I need integers $p$ and $q$ such that $\frac{p}{q} \approx x$, but as I understand continued fractions, $q$ wouldn't be an integer in most cases. – LarsH Mar 23 '16 at 13:23
• @D.W.: Based on Yuval's answer I'm starting to see how continued fractions might help. Thanks for the hint. – LarsH Mar 23 '16 at 13:54

The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A best rational approximation of $x$ is a rational number $p/q$ such that $\left|x-\frac{p}{q}\right| \leq \left|x-\frac{p'}{q'}\right|$ for all $q' \leq q$. Your $p/q$ is in particular a best rational approximation, so it would be one of the convergents.