2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – D.W. Mar 23 '16 at 12:05
  • $\begingroup$ @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. $\endgroup$ – LarsH Mar 23 '16 at 13:14
  • $\begingroup$ @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. $\endgroup$ – LarsH Mar 23 '16 at 13:23
  • $\begingroup$ @D.W.: Based on Yuval's answer I'm starting to see how continued fractions might help. Thanks for the hint. $\endgroup$ – LarsH Mar 23 '16 at 13:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. It sounds like best rational approximation was the term I was looking for. $\endgroup$ – LarsH Mar 23 '16 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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