Convert Decimal number into Fraction

Question

I am trying to convert decimal number into its fraction. Decimal numbers will be having a maximum 4 digits after the decimal place. example:- 12.34 = 1234/100 12.3456 = 123456/10000

my code :-

#include <stdio.h>
int main(void) {
  double a=12.34;
  int c=10000;
  double b=(a-floor(a))*c;
  int d=(int)floor(a)*c+(int)b; 
  while(1) {
     if(d%10==0) {
    d=d/10;
    c=c/10;
 }
 else break;
  }
  printf("%d/%d",d,c);
 return 0;
}

but I am not getting correct output, Decimal numbers will be of double precision only.Please guide me what I should do.

Solution 1

If your floating point number is x, then the numerator of the fraction over 10000 will be the integral part of (x + 0.00005) * 10000. It's up to you whether you want to reduce the fraction to simplest terms (i.e. divide out by the gcd of the numerator and denominator).

Solution 2

Here is the algorithm that I use. It's an iterative process that works as follows:

1. The initial approximation for the numerator is 1 and the denominator is 1 divided by the fraction portion of the floating point value. For example, when converting 0.06 to a fraction, the denominator = 1/0.06 = 16.66666667 (rounded to 17), thus the initial approximation is 1/17.
2. The difference between the floating point value and the the current approximation is computed. For the example, the difference is 1/17 - 0.06 = 0.058824 - 0.06 = -0.001176.
3. If the absolute value of the difference is less than the defined tolerance (i.e. 0.000005), then the iteration is terminated.
4. Use the difference computed in step 2 to improve approximation of fraction. This is done by converting the difference into a fraction and adding (or subtracting) to the current approximation. In the example, a negative difference indicates a low approximation -- thus difference needs to be added to current approximation. The difference fraction is the numerator = 1 and denominator = 1/0.001176 = 850 -- difference in fraction from is 1/850. The new approximation will be (1/17) + (1/850) = (850*1 + 17*1)/(850*17) = 867/14450.
5. Repeat steps 2 to 4 until solution found.
6. After solution found, the fraction can be reduced. For example, 867/14450 is exactly 0.06 and the iteration process is terminated. 867/14450 can be reduced to 3/50.

Some features of this method are:

• If the resulting fraction is 1/anything, the first approximation will be exact. For example, converting 0.25 to fraction, the first approximation will be 1/4. Thus further iterations are not needed.
• In majority (> 80%) of 1,000,000 test cases, convergence occurs in 2 iteration or less.
• For all test cases, the maximum number of iterations was 3.

I posted the code for this algorithm on github -- https://github.com/tnbezue/fraction

Solution 3

My solution is quite simple, "lazy", runs by iteration, nothing fancy.

In most languages that have a decent Math library, you'll need nothing more than the algo itself.

But in bc, you'll need to implement simple functions such as

int() to return integer part of a number ,
abs() to return absolute value ,
float() to return floating part of a number ,
round() to round to nearest integer.

If nothing is found after (1/eps) iterations, the loop breaks with the last result.

eps=10^-4 /*Tweak for more or less accuracy */

define int(x) {
  auto s ;
  s = scale ;
  scale = 0 ;
  x /= 1 ;
  scale = s ;
  return x ;
}
define round(x) { return int(x+.5-(x<0)) ; }
define abs(x) { if ( x < 0 ) x=-x ; return x ; }
define float(x) { return abs(x-int(x)) ; }

define void frac(x) {
    auto f, j, n, z ;
    f = float(x) ;    
    j = 1 / eps ;
    z = .5 ;
    if ( f != 0 ) {
        while ( ( n++ < j ) && ( abs( z - round(z) ) > eps ) ) z = n / f ;
        n -= 1 ;
        if ( x < 0 ) n = -n ;
        x = int(x)
        z = round(z) ;
        print n + x*z , "/" , z , " = "
        if ( x != 0 )  print x , " + " , n , "/" , z , " = "
    }
    print x+n/z , "\n" ;
}

With standard accuracy (eps=.0001), you can get this :

frac(-.714285)
-5/7 = -.71428571428571428571

sqrt(2)
1.414213562373
frac(sqrt(2))
19601/13860 = 1 + 5741/13860 = 1.414213564213

6-7/pi
3.77183080
eps=.000001 ; frac(6-7/pi)
1314434/348487 = 3 + 268973/348487 = 3.77183080

Solution 4

#include <stdio.h>

int main(void) {
    double a = 12.34;
    int c = 10000;
    double b = (a - floor(a)) * c;
    int d = (int)floor(a) * c + (int)(b + .5f); 
    printf("%f %d\n", b, d);

    while(1) {
       if(d % 10 == 0) {
           d = d / 10;
           c = c / 10;
       }
       else break;
    }
    printf("%d/%d\n", d, c);
    return 0;
}

The problem is that b was getting 3400.00 but when you do (int) b you are getting 3399, so you need to add 0.5 so the number can truncate to 3400.

Getting 3400.00 is different than having 3400, 3400.00 means that the number was round to 3400, that's why when you do (int) 3400.00 it assumes that the nearest integer (less than the number you are converting) is 3399, however, when you add 0.5 to that number the last the nearest integer is now 3400.

If you want to acquire a deeper understanding of floating point arithmetic read What Every Computer Scientist Should Know About Floating-Point Arithmetic

View more solutions