Decimal to fraction conversion

Question

I got the following question for an interview:

Program to change a decimal to the nearest fraction.

Example: 0.12345 => 2649/20000

0.34 => 17/50

What is the best approach to solve this?

Answer 1

An approach I would come up with this late is get rid of the decimals:

0.12345 = 0.12345/1 = 12345/100000

Then find the Greatest common divisor and divide both by it.

Answer 2

A decimal number is a fraction whose denominator is a power of ten (and similarly for any number base). So 0.34 is 34/100. Now just cancel the common factor, i.e. divide both numerator and denominator by their greatest common divisor.

You can find the GCD with a standard algorithm, which I leave to you to find.

Answer 3

http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF

In short:

Let X be our decimal value. Z₁ == X, D₀ == 0 and D₁ == 1.

Z_i+1 == 1 / (Z_i - IntPart(Z_i))

D_i+1 == D_i * IntPart(Z_i+1) + D_i-1

N_i+1 == Round(X * D_i+1)

When the algorithm has found, by iterating through these Z, D and N series from the fixed-point Z₁, an index i of the series producing an N_i and D_i such that N_i / D_i == X, we're done. If there is a de minimis error (epsilon) within which a lower-terms approximation is acceptable, that error can be incorporated into the comparison of the working fraction with the input.

Prior to that condition being met, the series Z tracks the continued fraction of the decimal value, and the algorithm uses this factor to increase the denominator of the fraction until sufficient precision is attained.

Understand that the input value is best stored as a decimal type, and the calculation of N/D should also result in a decimal type, to avoid floating point rounding error.

The solution:

public struct Fraction
{
    public int Numerator { get; private set; }
    public int Denominator { get; private set; }

    public Fraction(int num, int denom) 
    {
        Numerator = num;
        Denominator = denom;
    }
    public decimal DecimalValue 
    { 
        get { return ((decimal)Numerator) / Denominator; } 
    }
    public override string ToString()
    {
        return Numerator.ToString() + "/" + Denominator.ToString();
    }

    public static Fraction FromDecimal(decimal x, decimal epsilon = 0.0000001m)
    {
        decimal z = x;
        decimal dPrev = 0;
        decimal dCur = 1;
        decimal dTemp = dCur;
        decimal n = 0;

        while ((Math.Abs(n / dCur) - x) > epsilon)
        {
            z = 1 / (z - (int)z);
            dTemp = dCur;
            dCur = (dCur * (int)z) + dPrev;
            dPrev = dTemp;
            n = Math.Round(x * dCur);
        }

        return new Fraction((int) n, (int) dCur);
    }
}

This algorithm is capable of finding the "true" fractional values of rational numbers that are artificially terminated due to precision limitations (i.e. .3333333 would be 1/3, not 3333333/10000000); it does this by evaluating each candidate fraction to produce a value that would be subject to the same precision limitations as the input. It actually depends upon that; feeding this algorithm the true value of pi (if you could) would cause an infinite loop. However, this behavior creates a weakness in the algorithm when expecting arbitrarily-low epsilons (including zero); representations of irrational numbers, or of decimal values not exactly equal to the value produced by the division inherent in the fraction, can produce unexpected results.

Answer 4

Naive solution..

1. 0.12345 = 12345 / 100000
2. find greatest common divisor
3. divide both of the parts of fraction with the GCD
4. profit

Answer 5

First, make the numerator and denominator integral by multiplying continuously by ten.

So, 0.34/1 becomes 34/100, and 0.12345/1 becomes 12345/100000

Then use a GCD calculation to get the greatest common divisor of those two numbers, and divide them both by that.

The GCD of 34 and 100 is 2, which gives you 17/50. The GCD of 12345 and 1000000 is 5, which gives you 2469/20000.

A recursive GCD function in C is:

int gcd (int a, int b) {
    return (b == 0) ? a : gcd (b, a%b);
}

Answer 6

The answer by Kerrek SB is correct, but using continued fractions it is easy to find the best rational approximation of any real number (represented as a float or not), for any given maximal denominator. The optimal property of the method is described here: http://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems, theorem 4 and 5.

Example results: approximate sqrt(2) with a denominator less or equal to 23:

findapprox(math.sqrt(2),23)
          (3, 2)  new error frac: 6.0660e-02 
          (7, 5)  new error frac: 1.0051e-02 
        (17, 12)  new error frac: 1.7346e-03 
        (41, 29)  new error frac: 2.9731e-04 
result: (17, 12)

Example: approximate 23.1234 with denominator <=20000:

findapprox(23.1234,20000)
            (185, 8)  new error frac: 6.9194e-05 
          (1688, 73)  new error frac: 4.8578e-06 
          (1873, 81)  new error frac: 2.4560e-06 
         (3561, 154)  new error frac: 1.0110e-06 
         (5434, 235)  new error frac: 1.8403e-07 
        (19863, 859)  new error frac: 3.0207e-08 
       (25297, 1094)  new error frac: 1.5812e-08 
       (45160, 1953)  new error frac: 4.4287e-09 
       (70457, 3047)  new error frac: 2.8386e-09 
      (115617, 5000)  new error frac: 0.0000e+00 
result: (115617, 5000) (exact)

Continued fractions have some funky characteristics. For example sqrt(2) can be written as 1,2,2,,... meaning 1+1/(2+1/(2+1/...). So we can find optimal rational approximations for sqrt(2):

rewrap([1]+[2]*30) gives 367296043199 / 259717522849, 
all correct: 1.4142135623730951

Here's the code (python).

# make a+1/(b+1/(c+1/...)) cont fraction of a float
# no special care taken to accumulation of float truncation errors.
def contfrac(v):
    nums=None
    while nums==None or len(nums)<20:
        if not nums:
            nums=[]
        vi=int(v)
        v=v-vi
        nums.append(vi)
        if v<=0 : 
            return nums
        v=1.0/v
    return nums


# make tuple representing a rational number based on a cont f list 
# this is exact
def rewrap(v):
    rat=(0,1)
    first=1
    for k in reversed(v):
        if first:
            first=0
            rat=(k,1)
        else:            
            rat=(k*rat[0]+rat[1],rat[0])        
    return rat

# float evaluate a ratio
def makefloat(v):
    return v[0]*1.0/v[1]

# find the best rational approximation with denominator <=maxdenom
def findapprox(flt,maxdenom):
    flt=1.0*flt
    cf=contfrac(flt)
    best=(cf[0],1)
    errfrac=1e9
    for i in range(2,len(cf)):
        new=rewrap(cf[:i])        
        newerrfrac=abs((flt-makefloat(new))/flt)
        print "%20s"%(str(new)),
        print(" new error frac: %5.4e " %(newerrfrac))
        if new[1]>maxdenom or newerrfrac>errfrac:
            return best
        best=new
        errfrac=newerrfrac
        if newerrfrac ==0: 
            return best
    return best

Answer 7

1. get rid of dot : (0.a₁..a_n * 10ⁿ) / (1*10ⁿ)
2. x = GCD( a₁..a_n , 10ⁿ)
3. (a₁..a_n/x) / (10ⁿ/x)

foo(double a) {
    int digits = (int)log(a, 10);
    int x = GCD((int)(a * 10^digits) , 10^digits);
    return ((int)(a * 10^digits) / x) + " / " + (10^digits / x);    
}

Answer 8

First, convert your numbers to an obvious fraction

0.34 => 34/100

and

0.12345 => 12345/100000

Now reduce the fractions. You will need to find the GCD of the numerator and the denominator. The GDC of 34 and 100 is 2. Divide both numbers by 2 and you get 17/50.

See Greatest common divisor on Wikipedia. You will also find a brief description of an algorithm for GCD there.