test if a decimal is sufficiently close to a rational number

Question

Given a decimal x, I want to test if x is within 10^-12 of a rational number with denominator 9999 or less. Obviously I could do it by looking at x, 2x, 3x, and so on, and seeing if any of these is sufficiently close to an integer. But is there a more efficient algorithm?

Answer 1

There is an algorithm called the continued fraction algorithm that will give you "best" rational approximations in a certain defined sense. You can stop when your denominator exceeds 9999 and then go back to the previous convergent and compare to see if it is close enough. Of course if the decimal is a small enough rational number the algorithm will terminate early.

Answer 2

So, a couple of things:

I assume that by 'decimal x' you're referring to some floating point representation x. That is, you intend to implement this in some format that can't actually perfectly represent .1 or 1/3, etc. If you're doing this by hand or something else that has its own way to represent decimals, this won't apply.

Second, are you tied to those specific denominators and tolerances? I ask because if you're ok with powers of 2 (e.g. denominator up to 8192 with tolerance of 2^-35), you could easily take advantage of the fact that IEEE-754 style floating points are all rational numbers. Use the exponent to determine which digit in the mantissa corresponds to 2^-13, then ensure that the next 22 digits of the mantissa are 0 (or up to 22 if the precision isn't high enough to include 22 beyond that point). If so, you've got it.

Now, if you're not willing to alter your algorithm to use base 2, you could at least use this to narrow it down and do some elimination.

Answer 3

I see that you've already accepted an answer, but I'm going to chime in anyway.

The brute force method doesn't need to check every denominator. If you work your way backwards, you can eliminate not only the number you just checked but every factor of it. For example, once you've checked 9999 you don't need to check 3333, 1111, 909, 303, 101, 99, 33, 11, 9, 3, or 1; if the number can be expressed as a fraction of one of those, it can also be expressed as a fraction of 9999. It turns out that every number under 5000 is a factor of at least one number 5000 to 9999, so you've cut your search space in half.

Edit: I found this problem interesting enough to code a solution in Python.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def simplify(fraction_tuple):
    divisor = gcd(fraction_tuple[0], fraction_tuple[1])
    return fraction_tuple[0] / divisor, fraction_tuple[1] / divisor

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False):
    best_error, best_result = abs(value), (0,1)
    for denominator in range(max_denominator/2+1, max_denominator+1):
        numerator = round(value * denominator)
        error = abs(value - (numerator / denominator))
        if error < best_error:
            best_error = error
            best_result = int(numerator), denominator
            if error <= tolerance:
                break
    if enforce_tolerance and best_error > tolerance:
        return None
    return simplify(best_result)