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 you have 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 to the desired precision, you're done.

Understand that the decimal 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 decimal DecimalValue { get { return ((decimal)Numerator) / Denominator; } }
    public override string ToString()
    {
        return Numerator.ToString() + "/" + Denominator.ToString();
    }

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

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

        return new Fraction {Numerator = (int) n, Denominator = (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. It actually depends upon that; feeding this algorithm the true value of pi (if you could) would cause an infinite loop.

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.