Optimized algorithm for converting a decimal to a "pretty" fraction_问答_开发者

Rather than converting an arbitrary decimal to an exact fraction (something like 323527/4362363), I am trying to convert to just common开发者_开发技巧 easily-discernible (in terms of human-readability) quantities like 1/2, 1/4, 1/8 etc.

Other than using a series of if-then, less than/equal to etc comparisons, are there more optimized techniques to do this?

Edit: In my particular case, approximations are acceptable. The idea is that 0.251243 ~ 0.25 = 1/4 - in my usage case, that's "good enough", with the latter more preferable for human readability in terms of a quick indicator (not used for calculation, just used as display numerics).

Look up "continued fraction approximation". Wikipedia has a basic introduction in its "continued fraction" article, but there are optimized algorithms that generate the approximated value while generating the fraction.

Then pick some stopping heuristic, a combination of size of denominator and closeness of approximation, for when you're "close enough".

You can use Euclidean algorithm to get Greatest Common Divisor between enumerator and denominator and divide them by it.

In the following, I'm going to assume that our decimals fall in between 0 and 1. It should be straightforward to adapt this to larger numbers and negative numbers.

Probably the easiest thing to do would be to choose the largest denominator that you would find acceptable and then create a list of fractions between 0 and 1 which have that denominators less than or equal to them. Be sure to avoid any fractions which can be simplified. Obviously, once you've listed 1/2, you don't need 2/4. You can avoid fractions which can be simplified by checking that the GCD of the numerator and denominator is 1 suing Euclid's algorithm. Once you have your list. Evaluate these as floating point numbers (probably doubles, but the data type obviously depends on your choice of programming language). Then insert them into a balanced binary search tree storing both the original fraction and the floating point evaluation of the fraction. You should only need to do this once to set things up initially so the n*log(n) time (where n is the number of fractions) isn't very much.

Then, whenever you get a number, simply search the tree to find the closest number to it which is in the search tree. Note that this is slightly more complicated than searching for an exact match because the node you're looking for may not be a leaf node. So, as you traverse the tree keep a record of the closest valued node that you have visited. Once you reach a leaf node and compare that one to your closest valued node that you have visited, you are done. Whichever your closest one is, it's fraction is your answer.

Here is a suggestion: Assuming your starting fraction is p/q

Calculate r = p/q as a rational(floating point) value (e.g. r = float(p)/float(q))
Calculate the rounded decimal x = int(10000*r)
Calculate GCD (greatest common denominator) of x and 10000: s = GCD(x, 10000)
Represent the result as m / n where m = x/s and n = y/s (your example computes to 371 / 5000)

Normally, all denominators of 1000 are fairly human readable.

This might not provide the best result when the value is closer to simpler cases such as 1/3. However, I personally find 379/1000 much more human readable than 47/62 (which is the shortest fractional representation). You can add a few exceptions to fine tune such process though (e.g. calculating the p/GCD(p,q) , q/GCD(p,q) and accepting it if one of those are single digit values before proceeding to this method)

Pretty dumb solution, just for "previewing" fraction :

factor = 1/decimal
result = 1/Round(factor)
mult = 1

while (result = 1) {
  mult = mult * 10
  result = (1 * mult)/(Round(mult * factor))
}

result = simplify_with_GCD(result)

good luck!