CODEWITHSUNDEEP
algorithmmathfractions
Abyssal
Abyssal

Reputation: 53

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

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?

Upvotes: 5

Views: 349

Answers (3)

David Heffernan
David Heffernan

Reputation: 613442

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.

Upvotes: 7

Mike Bailey
Mike Bailey

Reputation: 12817

As suggested in the comments, your best bet is to use Ceiling and Floor functions.

If your rational a / b is given as 0 <= x <= 1 then you can simply do this:

int Rationalize(double x)
{
    int n1 = floor(1 / x);
    int n2 = ceiling(1 / x);

    double e1 = abs(x - 1.0 / n1);
    double e2 = abs(x - 1.0 / n2);

    if (e1 < e2) return n1;
    else return n2;
}

(Where it's assumed abs, floor, and ceiling are predefined)

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373082

I believe that you can do this in O(1) by using continued fractions. Any rational number in the range (0, 1] can be written in the form

1 / (a0 + 1 / (a1 + 1 / (a2 + 1 / (... an))))

Moreover, this representation has some remarkable properties. For starters, if you truncate the representation at any point, you get an extremely good approximation to the rational number. In particular, if you just truncate this representation at

1 / a0

Then the fraction a/b will be between 1/a0 and 1/(a0+1). Consequently, if we can get the value of a0, then you can just check the above two numbers to see which is closer.

The second important property is that there is a great way of obtaining the value of a0: it's given by the quotient of b/a. In other words, you can find the closest fraction as follows:

  1. Compute x = b / a using integer division.
  2. Check whether 1/x or 1/(x+1) is closer to a/b and output that result.

If a and b fit into machine words, this runs in O(1) time.

Upvotes: 1

Related Questions