Geek Answers Handbook

Optimized decimal fraction conversion algorithm to a "pretty" fraction

Instead of converting an arbitrary decimal number to an exact fraction (something like 323527/4362363), I try to convert only the usual easily distinguishable (in terms of credibility) quantities, such as 1/2, 1/4, 1/8, etc. .

Besides using a series of comparisons if-then, less or / to, etc., are there more optimized methods for this?

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

+5
source share
5 answers

See "fractional fraction approximation." Wikipedia has a basic introduction to the article “continued fractions”, but there are optimized algorithms that generate an approximate value when creating fractions.

Then select some inhibitory heuristic, a combination of denominator size and approximation proximity when you are "close enough".

+7
source

You can use the Euclidean algorithm to get the Greatest common factor between the enumerator and the denominator and divide them into it.

+3
source

, 0 1. .

, , , 0 1, , . , . , , 1/2, 2/4. , , , GCD - 1, . , . (, , , , ). , , . , , n * log (n) ( n - ) .

, , , , , . , , , node, , node. , , , node, . node node, , . , .

0

: , p/q

  • r = p/q ( ) (, r = float (p)/float (q))

  • x = int (10000 * r)

  • GCD ( ) x 10000: s = GCD (x, 10000)

  • m/n, m = x/s n = y/s ( 371/5000)

1000 .

, , 1/3. , 379/1000 , 47/62 ( ). (, p/GCD (p, q), q/GCD (p, q) , , )

0

Pretty dumb solution, just for a “preview”:

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

0
source

More articles:


All Articles