Rounding rationals in (0, 1) to the nearest unit fraction

Question

What's a good algorithm for the following problem?

Given a rational a / b strictly between 0 and 1, find a natural n that minimizes |a / b - 1 / n|.

The simplest algorithm I can think of is to compare a / b and 1 / m for m = b, b - 1, …, stopping when a / b ≤ 1 / m, and then compare |a / b - 1 / m| and |a / b - 1 / (m + 1)|. That's O( b ). Can you do any better?

Answer 1

Let k = floor(b/a) and then n must equal either k or k+1. Try the 2 candidates and see which one wins. This is O(1).

That this is true follows from the fact that 1/(k+1) <= a/b <= 1/k which in turn follows from the inequalities k <= b/a <= k+1.