Find $x, y$ such that $\left | \frac ab -\frac xy \right |$ is minimal Given positive integers $a, b, D$. How to find $x, y \in \mathbb{Z^+}$ such that $$M =\left |  \frac ab -\frac xy \right |$$ is minimal and $x + y \le D$?

For a solution, I can get it by brute-force but I can't find efficient way to solve this problem.
 A: Let's assume $q=\frac{a}{b}\notin\mathbb{N}$. Let $n=\lfloor q\rfloor$, then we can trivially approximate $q$ by $x=n$ and $y=1$. Notice that the higher we can take $y$, the better the approximation will be, but how high we can go is constrained by $D$. Also, if $y=k$, then if we want to go as close as possible to $q$ we will certainly need $x\ge kn$. This immediately gives us:
$$k(n+1)\le x+y\le D$$
Equivalently:
$$k\le\frac{D}{n+1}$$
Similarly, considering the ceiling instead of the floor above, $n+1=\lceil q\rceil$, we obtain the bound for $y=k$:
$$x+y\le k(n+2)$$
So now I would do it as follows:


*

*Take $k=\left\lfloor\frac{D}{n+1}\right\rfloor$, if $k(n+2)\le D$ then simply check for $y=k$ and $x$ running from $kn$ and $k(n+1)$.

*Else if $k(n+2)> D$, do the same as before, keep the best solution found with $x+y\le D$ and then repeat with $k=k-1$ and so on until $k(n+2)$ drops below $D$, always keep the best solution.


I seriously doubt this is optimal, but it certainly work much better than simple bruteforce.

Edit: The second step should translate to: do the first step for:
$$\left\lfloor\frac{D}{n+2}\right\rfloor\le k\le\left\lfloor\frac{D}{n+1}\right\rfloor$$
which should include at most the numbers $\left\lfloor\frac{D}{n+1}\right\rfloor$ and $\left\lfloor\frac{D}{n+1}\right\rfloor-1$. Thus you will basically need to check:
$$2\left\lfloor\frac{D}{n+1}\right\rfloor-1=O\left(\frac{D}{\lfloor q\rfloor}\right)$$
fractions (worst case scenario).
