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.

Improve this question
$\endgroup$
4
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 13:54

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. It sounds like best rational approximation was the term I was looking for. $\endgroup$
    – LarsH
    Mar 23, 2016 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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