# test if a decimal is sufficiently close to a rational number

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?

-

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.

-

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.

-
How does this help me for something like 3/7? –  William Jockusch Oct 14 '10 at 2:17
You've specified that your input is a decimal (and I assumed one of finite length), so I'm not sure what you mean exactly (since 3/7 is a repeating decimal, I suppose you could run it out to some number of digits, then test that) –  Dusty Oct 14 '10 at 2:44
What he means is that an input of 0.4285714285714 should return 3/7 because it is within 10^-12 of 3/7. –  Mark Ransom Oct 14 '10 at 4:18
@Mark - Ah, I didn't read into it that he wanted it to return which rational number. –  Dusty Oct 14 '10 at 11:33

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)
``````
-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}