Algorithm for simplifying decimal to fractions

by

The algorithm that the other people have given you gets the answer by calculating the Continued Fraction of the number. This gives a fractional sequence which is guaranteed to converge very, very rapidly. However it is not guaranteed to give you the smallest fraction that is within a distance epsilon of a real number. To find that you have to walk the Stern-Brocot tree.

To do that you subtract off the floor to get the number in the range [0, 1), then your lower estimate is 0, and your upper estimate is 1. Now do a binary search until you are close enough. At each iteration if your lower is a/b and your upper is c/d your middle is (a+c)/(b+d). Test your middle against x, and either make the middle the upper, the lower, or return your final answer.

Here is some very non-idiomatic (and hence, hopefully, readable even if you don’t know the language) Python that implements this algorithm.

def float_to_fraction (x, error=0.000001):
    n = int(math.floor(x))
    x -= n
    if x < error:
        return (n, 1)
    elif 1 - error < x:
        return (n+1, 1)

    # The lower fraction is 0/1
    lower_n = 0
    lower_d = 1
    # The upper fraction is 1/1
    upper_n = 1
    upper_d = 1
    while True:
        # The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
        middle_n = lower_n + upper_n
        middle_d = lower_d + upper_d
        # If x + error < middle
        if middle_d * (x + error) < middle_n:
            # middle is our new upper
            upper_n = middle_n
            upper_d = middle_d
        # Else If middle < x - error
        elif middle_n < (x - error) * middle_d:
            # middle is our new lower
            lower_n = middle_n
            lower_d = middle_d
        # Else middle is our best fraction
        else:
            return (n * middle_d + middle_n, middle_d)

More Related Contents:

  1. C# custom add in a List
  2. Math.Round doesn’t behave like i want it to. (X.0xxxxx numbers) [closed]
  3. Best way to reverse a string
  4. How to check if a number is a power of 2
  5. Algorithm to detect overlapping periods [duplicate]
  6. All Possible Combinations of a list of Values
  7. Best way to randomize an array with .NET
  8. What guarantees are there on the run-time complexity (Big-O) of LINQ methods?
  9. C# Point in polygon
  10. Remove text in-between delimiters in a string (using a regex?)
  11. Algorithm to find which numbers from a list of size n sum to another number
  12. Double precision problems on .NET
  13. How Math.Pow (and so on) actually works
  14. Best way to find all factors of a given number
  15. Split String into smaller Strings by length variable
  16. Compare string similarity
  17. Calculate median in c#
  18. How to force a number to be in a range in C#? [duplicate]
  19. C#: Seeking PNG Compression algorithm/library [closed]
  20. How can I generate truly (not pseudo) random numbers with C#?
  21. What’s the quickest way to compute log2 of an integer in C#?
  22. What is the fastest way to compute sin and cos together?
  23. How can I tell if a point belongs to a certain line?
  24. Creating a power set of a Sequence
  25. All cases covered Bresenham’s line-algorithm [closed]
  26. Algorithm for Calculating Binomial Coefficient
  27. Fastest implementation of log2(int) and log2(float)
  28. Best algorithm for evaluating a mathematical expression?
  29. Why does Math.Exp give different results between 32-bit and 64-bit, with same input, same hardware
  30. How to round a integer to the close hundred?

Leave a Comment