C Fraction Arithmetic

Question

I'm having great difficulty with the following that I need to do for an assign:
a. Declare a data structure that contains a rational number.
b. Write f'xns that will +, -, *, / rational numbers.
All f'xns have to pass 3 parameters, each pointing to a data structure of the type I declared in part a; 2 of the parameters = operands, 3rd = result.
c. Write a f'xn that takes a pointer to your data structure as a parameter and returns the GCD of the numer. & denom.
d. Use your f'xn from part c to write a f'xn that will reduce a fraction (rational number) to lowest terms. Pass in a pointer to the fraction and have the fraction modified by the f'xn.
e. Write input and output functions so that a user can enter a fraction in the form 1/5 for example.

The user should be allowed to enter any number of problems, and the program should output the answer in lowest terms.

Am I on the right track? I believe I have a-c down, but not d and especially e. Can someone please guide me or help me correct my script?

int GCD (int numer, int denom)
{
    int result;
    while (denom > 0) {
        result = numer % denom;
        numer = denom;
        denom = result;
    }
    return numer;
}

int getLCM (int numer, int denom)
{
    int max;
    max = (numer > denom) ? numer : denom;
    while (1) {
        if (max % numer == 0 && max % denom == 0)
            break;
        ++max;
    }
    return max;
}

struct Fraction 
{
    int numer;
    int denom;
};

typedef struct 
{
    int numer;
    int denom; 
};
Fraction

Fraction add_fractions (Fraction a, Fraction b)
{
    Fraction sum;
    sum.numer = (a.numer * b.denom) + (b.numer * a.denom);
    sum.denom = a.denom * b.denom;
    return sum;
}

Fraction subtract_fractions (Fraction a, Fraction b)
{
    Fraction sum;
    sum.numer = (a.numer * b.denom) - (b.numer * a.denom);
    sum.denom = a.denom * b.denom;
    return sum;
}

Fraction multiply_fractions (Fraction a, Fraction b)
{
    Fraction sum;
    sum.numer = (a.denom * b.denom);
    sum.denom = (a.numer * b.numer);
    return sum;
}

Fraction divide_fractions (Fraction a, Fraction b)
{
    Fraction sum;
    sum.numer = (a.denom * b.numer);
    sum.denom = (a.numer * b.denom);
    return sum;
}

int main ()
{
    char response;

    printf ("FRACTION ARITHMETIC PROGRAM\n");
    printf ("Enter your problem (example 2/3 + 1/5):\n");
    scanf (, &problem);

    if (denom == 0 || denom < 0) {
        printf ("Illegal input!!\n");
        printf ("Another problem (y/n)?  ");
        scanf ("%c%*c", &response);
    } else {
        printf ("The answer is  ");

        printf ("Another problem (y/n)?  ");
        scanf ("%c%*c", &response);
    }

    while ((response == 'y') || (response == 'Y')) {
        printf ("\nWould you like to play again?\n");
        scanf ("%c%*c", &response);
    }

    while ((response == 'n') || (response == 'N'))
        printf ("Goodbye and thank you");

    return 0;
}

Edit after removing typedef thanks to comment responses:

struct Fraction {
    int numer;
    int denom;
};

struct Fraction add_fractions (struct Fraction a, struct Fraction b)
{
    struct Fraction sum;
    sum.numer = (a.numer * b.denom) + (b.numer * a.denom);
    sum.denom = a.denom * b.denom;
    return sum;
}

struct Fraction subtract_fractions (struct Fraction a, struct Fraction b)
{
    struct Fraction sum;
    sum.numer = (a.numer * b.denom) - (b.numer * a.denom);
    sum.denom = a.denom * b.denom;
    return sum;
}

struct Fraction multiply_fractions (struct Fraction a, struct Fraction b)
{
    struct Fraction sum;
    sum.numer = (a.denom * b.denom);
    sum.denom = (a.numer * b.numer);
    return sum;
}

struct Fraction divide_fractions (struct Fraction a, struct Fraction b)
{
    struct Fraction sum;
    sum.numer = (a.denom * b.numer);
    sum.denom = (a.numer * b.denom);
    return sum;
}

Intellectualism

To my understanding, you are somewhat on the right track; however you could introduce a function to reduce the fractions to prevent the values in the numerator and denominator too quickly. – Conjugate

The type struct Fraction is wholly unrelated to the type Fraction, which is an anonymous (untagged) structure type with a typedef name of Fraction. You should probably combine the two, though either one could be used. What's erroneous is having both. – Machismo

You can do better in getLCM function. It would be a good idea to normalize fraction before returning by diving numer and denom with gcd. (Write a function to normalize) Either typedef or struct Fraction can be removed to avoid confusion. – Bradfordbradlee

Note that the specification says that the operation functions will take three parameters — two (constant) pointers to the operands and a pointer to the result (and presumably the return type is void, though it could be a success/failure indicator showing whether the result could be stored). Your functions implement a more useful and usable scheme where the parameters are passed by value and the result is returned by value. However, that's not the spec. Beware of nitpicking teachers. You have similar issues with your GCD function; the specification says one interface, but you have another. – Machismo

Additionally note that there were a number of statement nesting errors in the original code posted. The code has been reformatted to indent properly, which required correcting the nesting errors (e.g. mismatched { { }...), but the original content was preserved. – Bolus

Thanks, David! I removed typedef for now. In summary, I guess I'll need a fx'n that reduces the fractions, a better getLCM function, a fix for the GCD function fix, and a fix for the specific parameter requirements... Thanks, guys! – Intellectualism

Assuming 32-bit integers, when you add 1/100000 and 1/100000, your implementation will have an integer overflow, because (100000)^2 is more than a 32-bit int can handle. Yet the final result is 1/50000 which is representable in your implementation. – Season

@Anonymissy, that is somewhat of a No-No... You are free to edit your question, but you need to paste new code below the original (or just include a statement at the end Removed Code and list the typedef) Why? Well look at Johnathan's comment now (the 2nd). It now makes no sense because the code it referred to in the Question is gone... Anybody else that comes along in the future to learn from the question will be left scratching his head wondering what the heck that comment is all about. Now it's not a killing offense, but some people are touchy about it. Just something you have to learn. – Bolus

No worries, reverted the answer back to the original and added the edit below. Thanks for letting me know! – Intellectualism

Answer 1

Some remarks with your code:

• You do not thoroughly follow your requirements because GCD function takes 2 integers when it is required to take a pointer to struct, and your functions take 2 struct as parameter and return another one when they should take 3 (pointers to) structs.
• Your GCD function uses a nice GCD implementation (thanks to Jonathan for its comment), even if some comment explaining the why would be nice for future readers
• As you were said in comment, you should reduce rationals before doing operations on them to avoid unnecessary overflows, and when adding or subtracting rationals, you should use the LCM of the denoms for same reason
• Your LCM algorithm is poor. As your GCD is nice why not simply use: LCM(a,b) = a * b / GCD(a,b) computed as lcm = (a/gcb) * b to reduce overflow risk (thanks to @n.m. for the simplified form)
• Reduced form of a/b is a'/b' where a'=a/GCD(a,b) and b'=b/GCD(a,b)
• What about a "%d/%d" format for both input and output, with the two members of a struct?

Last but not least, format "%c%*c" to get answer to a y/n question is possible but dangerous: you are likely to get the newline of preceding input into response! Choose one of line oriented input (with fgets + sscanf) or free form input (with scanf or fscanf) and stick to it. %1s into a char response[2] is much safer...

And carefully write in comment that you only process positive rationals or take care of sign! Such a detail can make users of a library rather angry ... not to mention nitpicking teachers (credits for Jonathan Leffler).

Foregoing

"why not simply use: LCM(a,b) = a * b / GCD(a,b) ". Because overflow. – Season

@n.m.: the overflow problem is already taken into account in the end of the sentence. And if lcm = (a/gcb) * (b/gcd) * gcd overflows, nothing else can be done! – Foregoing

Sorry, my attention span is restricted today... why not just a / gcd(a,b) * b? – Season

As a point of detail, if you start the GCD with { 6, 4 } instead of { 4, 6 } (or vice versa), the first iteration effectively does the swap anyway and the result is correct. Try it. So that swap is not necessary; it clutters otherwise clean code at the cost of a division/modulus operation instead of a comparison. – Machismo

Answer 2

You can use an enum for operators and a function to switch on the operators since all operators follow a similar pattern. This simplifies the code. Here is example of some of the implementations, you can add the rest:

typedef struct node {
    int nom;
    int denom;
} Tfraction;

typedef enum {PLUS, MINUS, MULTIPLY, DIVIDE} Ops;

int calculate(int x, Ops op, int y) {
    switch (op) {
        case PLUS: return x + y;
        case MINUS: return x - y;
        case MULTIPLY: return x * y;
        case DIVIDE: return x / y;
    }
}

//reccursive gcd
int gcdr (int a, int b) {
    if (a == 0) return b;
    return gcdr(b % a, a);
}

void simplify(Tfraction *fraction) {
    int gcd = gcdr(fraction->nom, fraction->denom);
    fraction->nom /= gcd;
    fraction->denom /= gcd;
}

Tfraction compute(Tfraction a, Tfraction b, Ops op) {
    if (op == DIVIDE) {
        int temp = b.nom;
        b.nom = b.denom;
        b.denom = temp;
        op = MULTIPLY;
    }

    if (op == MULTIPLY) {
        Tfraction result = { calculate(a.nom, op, b.nom), calculate(a.denom, op, b.denom) };
        simplify(&result);
        return result;
    }
    if (a.denom == b.denom) {
        Tfraction result = { calculate(a.nom, op, b.nom), a.denom };
        simplify(&result);
        return result;
    }
    else {
        Tfraction result = { (calculate((a.nom * b.denom), op, (b.nom * a.denom))), (a.denom * b.denom) };
        simplify(&result);
        return result;
    }
}

int main ()
{
    //Test
    Tfraction f1 = {2, 4}, f2 = {4, 2};

    printf("Addition: %d/%d\n", compute(f1, f2, PLUS).nom, compute(f1, f2, PLUS).denom);
    printf("Subtraction: %d/%d\n", compute(f1, f2, MINUS).nom, compute(f1, f2, MINUS).denom);
    printf("Multiplication: %d/%d\n", compute(f1, f2, MULTIPLY).nom, compute(f1, f2, MULTIPLY).denom);
    printf("Division: %d/%d\n", compute(f1, f2, DIVIDE).nom, compute(f1, f2, DIVIDE).denom);

    return 0;
}

Overdevelop

I don't think your simplify code is remotely valid. Consider a fraction presented as 15 / 9; you should end up with 5 / 3, but your code would yield 2 / 1, which is not the same thing at all. – Machismo

I fixed it. there might be some improvements in the implementation but I was emphasizing on the logic. simplification isn't even in the question so you shouldn't down vote just for that – Overdevelop

Bullets (c) and (d) in the question are about simplifying fractions. Your 'fixed' code is still wrong. You need to be using GCD and/or LCM and you are not. You have also not attempted to follow the specification in the question w.r.t functions taking three pointers, one per operation. – Machismo

Sorry about that, I fixed it. – Overdevelop

The simplify code still isn't correct. Given 48 / 12 to simplify, it divides by 2 and exits the loop, leaving 12 / 6 instead of dividing by another factor of 2 and a factor of 3 to leave 4 / 1. – Machismo

No it doesn't give 12 / 6. run it again. It does give 4 / 1. It starts from the biggest dividers until it hits a common one for both denom and nominator so it won't loop until 2 in this case – Overdevelop

I stand corrected — it does yield the correct result. However, it is not as efficient as using a GCD calculation. For example, if the fraction is 36/33, it will attempt 62 modulo operations before finding that 3 is the common divisor. Using GCD, that would be 3 modulo operations. Euclid was pretty clever when he discovered and recorded the GCD algorithm 2300-odd years ago. – Machismo

You're right, I didn't know about that. Thanks I changed it ;) – Overdevelop

Answer 3

I changed the sum and multiply functions to minimize overflow, although I did not change them to accept 3 arguments (I prefer this way).

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int numer;
    int denom; 
} Fraction;

int gcd(int numer, int denom) {
  int result;
  while (denom != 0) {
    result = numer % denom;
    numer = denom;
    denom = result;
  }
  return numer;
}

int lcm(int a, int b) {
  return (a / gcd(a,b)) * b;
}

Fraction simplify (Fraction a) {
  int cd;
  cd = gcd(a.numer, a.denom);
  a.numer /= cd;
  a.denom /= cd;
  return a;
}

Fraction add_fractions (Fraction a, Fraction b) {
  Fraction sum;
  int lcmd;
  a = simplify(a);
  b = simplify(b);
  lcmd = lcm(a.denom, b.denom);
  sum.numer = (lcmd / a.denom * a.numer) + (lcmd / b.denom * b.numer);
  sum.denom = lcmd;
  return simplify(sum);
}

Fraction subtract_fractions (Fraction a, Fraction b) {
  Fraction sum;
  int lcmd;
  a = simplify(a);
  b = simplify(b);
  lcmd = lcm(a.denom, b.denom);
  sum.numer = (lcmd / a.denom * a.numer) - (lcmd / b.denom * b.numer);
  sum.denom = lcmd;
  return simplify(sum);
}

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

Fraction multiply_fractions (Fraction a, Fraction b) {
  Fraction sum;
  a = simplify(a);
  b = simplify(b);
  swap(&a.numer, &b.numer); // another round of simplifications to avoid (minimize) overflows below
  a = simplify(a);
  b = simplify(b);
  sum.numer = (a.numer * b.numer);
  sum.denom = (a.denom * b.denom);
  return sum;
}

Fraction divide_fractions (Fraction a, Fraction b) {
  swap(&b.numer, &b.denom);
  return multiply_fractions(a, b);
}

int main() {
  int a, b;
  Fraction f1 ,f2, res;

  printf("gcd(12,9)=%d\n", gcd(12,9));
  printf("gcd(9,12)=%d\n", gcd(9,12));

  printf("gcd(4,12)=%d\n", gcd(4,12));

  printf("gcd(8,12)=%d\n", gcd(8,12));
  printf("gcd(12,8)=%d\n", gcd(12,8));

  puts("-");

  printf("lcm(12,9)=%d\n", lcm(12,9));
  printf("lcm(9,12)=%d\n", lcm(9,12));

  printf("lcm(8,12)=%d\n", lcm(8,12));
  printf("lcm(12,8)=%d\n", lcm(12,8));

  printf("lcm(4,12)=%d\n", lcm(4,12));
  printf("lcm(3,5)=%d\n", lcm(3,5));
  printf("lcm(4,5)=%d\n", lcm(4,5));
  printf("lcm(3,4)=%d\n", lcm(3,4));

  puts("-");

  f1.numer = 12;
  f1.denom = 9;
  printf(" %d/%d simplified to", f1.numer, f1.denom);
  f1 = simplify(f1);
  printf(" %d/%d \n", f1.numer, f1.denom);

  f1.numer = 8;
  f1.denom = 12;
  printf(" %d/%d simplified to", f1.numer, f1.denom);
  f1 = simplify(f1);
  printf(" %d/%d \n", f1.numer, f1.denom);

  puts("-");

  f1.numer = 1; f1.denom = 4;
  f2.numer = 1; f2.denom = 4;
  res = add_fractions(f1, f2);
  printf(" %d/%d + %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 1; f1.denom = 4;
  f2.numer = 1; f2.denom = 12;
  res = add_fractions(f1, f2);
  printf(" %d/%d + %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 1; f1.denom = 3;
  f2.numer = 5; f2.denom = 6;
  res = add_fractions(f1, f2);
  printf(" %d/%d + %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 35; f1.denom = 100;
  f2.numer = 1; f2.denom = 4;
  res = subtract_fractions(f1, f2);
  printf(" %d/%d - %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 7; f1.denom = 10;
  f2.numer = 1; f2.denom = 2;
  res = subtract_fractions(f1, f2);
  printf(" %d/%d - %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 1; f1.denom = 2;
  f2.numer = 1; f2.denom = 2;
  res = multiply_fractions(f1, f2);
  printf(" %d/%d x %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 12; f1.denom = 5;
  f2.numer = 5; f2.denom = 6;
  res = multiply_fractions(f1, f2);
  printf(" %d/%d x %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 12; f1.denom = 21;
  f2.numer = 7; f2.denom = 4;
  res = multiply_fractions(f1, f2);
  printf(" %d/%d x %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

  f1.numer = 1; f1.denom = 5;
  f2.numer = 1; f2.denom = 5;
  res = divide_fractions(f1, f2);
  printf(" %d/%d / %d/%d = %d/%d \n", f1.numer, f1.denom, f2.numer, f2.denom, res.numer, res.denom);

}

Pleiades