Convert decimal to fraction (rational number) in O

Question

As part of a calculator app, I am trying to implement uses with sigma notation. However, the result it prints out is always a decimal, and the rest isn't important. I simply want to change the decimal to a fraction.

I already have the reduce function, the problem I'm having is getting from a decimal like this: '0.96875' to it's fractional value, '31/32'

Thanks!

PS: I've looked into just about everything, and for the life of me, I can't figure this out. All I need at this point is how to take the decimal out of it, and I can then reduce it.

Here is my reduce method:

    -(void)reduce {

    int u = numerator;
    int v = denominator;
    int temp;

    while (v != 0) {
        temp = u % v;
        u = v;
        v = temp;
    }

    numerator /= u;
    denominator /= u;

}

Answer 1

I found a fairly good way of doing this a while back, although I don't recall where from. Anyway, it works recursively like this (this is pseudocode, not C):

function getRational(float n)
  let i = floor(n); (the integer component of n)
  let j = n - i;
  if j < 0.0001 (use abritrary precision threshold here), return i/1
  let m/n = getRational(1 / j)
  return ((i * m) + n) / m

For example, take 3.142857 as a starting point.

i = 3
j = 0.142857
m/n = getRational(7)
  i = 7
  j = 0
  return 7/1
m/n = 7/1
return ((3*7)+1) / 7 = 22/7

Or a more complicated example, 1.55:

i = 1
j = 0.55
m/n = getRational(1.81818181)
  i = 1
  j = 0.81818181
  m/n = getRational(1.22222222)
    i = 1
    j = 0.22222222
    m/n = getRational(4.5)
      i = 4
      j = 0.5
      m/n = getRational(2)
        i = 2
        j = 0
        return 2/1
      m/n = 2/1
      return ((4*2)+1)/2 = 9/2
    m/n = 9/2
    return ((1*9)+2)/9 = 11/9
  m/n = 11/9
  return ((1*11)+9)/11) = 20/11
m/n = 20/11
return ((1*20)+11)/20 = 31/20

I tried this with PI once. It would have gone on a while, but if you set your threshold to 0.01, it only goes down a few recursions before returning 355/113.

There's a bit of a gotcha that you might end up with integers that are too large if it goes down too deep when it returns; I haven't really looked into a good way of allowing for that, except setting the precision threshold to something fairly lax, such as 0.01.

Answer 2

Found this out myself. What I did was multiply the numerator and denominator by 1000000 (recalling that the decimal looked like .96875/1) so that it looked like 96875/100000.

Then, I used this reduce method to bring it into lowest terms:

    -(void)reduce {

    int u = numerator;
    int v = denominator;
    int temp;

    while (v != 0) {
        temp = u % v;
        u = v;
        v = temp;
    }

    numerator /= u;
    denominator /= u;

}

And finally,I used a print method to get it into fraction form:

//In the .h
@property int numerator, denominator, mixed;
-(void)print;

//In the .m       
@synthesize numerator, denominator, mixed;

-(void)print {
    if (numerator > denominator) {
        //Turn fraction into mixed number
        mixed = numerator/denominator;
        numerator -= (mixed * denominator);
        NSLog(@"= %i %i/%i", mixed, numerator, denominator);
    } else if (denominator != 1) {
        //Print fraction normally
        NSLog(@"= %i/%i", numerator, denominator);
    } else {
        //Print as integer if it has a denominator of 1
        NSLog(@"= %i", numerator);
    }
}

And got my desired output:

31/32

Answer 3

Try this :

-(NSString *)convertToFraction:(CGFloat)floatValue{
    double tolerance = 1.0E-6;
    CGFloat h1 = 1;
    CGFloat h2 = 0;
    CGFloat k1 = 0;
    CGFloat k2 = 1;
    CGFloat b = floatValue;
    do{
        CGFloat a = floor(b);
        CGFloat aux = h1;
        h1 = a*h1+h2;
        h2 = aux;
        aux = k1;
        k1 = a*k1+k2;
        k2 = aux;
        b = 1/(b-a);
    }while (ABS(floatValue-h1/k1) > floatValue*tolerance) ;

    return k1 > 1 ?  [NSString stringWithFormat:@"%.0f/%.0f",h1,k1] : [NSString stringWithFormat:@"%.0f",h1];
}