reduce fraction

In the last article I’ve described Euclid’s algorithm for finding the greatest common divisor of two given numbers .A simple programming exercise I found in the book called “Algorithms in C” (Sedgewick) asks us to reduce a given fraction to lowest terms, using the Euclid’s Algorithm .

Eg.
Fraction = 36 / 120
Fraction = Reduce(Fraction) = 3 / 12

1. C Implementation

Step 1:

We will start by defining the data-structure we will use for encapsulating the fraction information (numerator and denominator):

/**
* Fraction data-structure:
* f = numerator / denominator
*/
typedef struct s_fraction {
  int numerator;
  int denominator;
} Fraction;

Step 2:

Usually when we play with C structures we should have two functions, for allocating and de-allocating memory associated with a structure (if you have an object-oriented background, this step will be equivalent with writing a constructor / destructor pair ) .

/**
* Allocates memory for a fraction structure .
* Initialize fraction structure .
* @param numerator
* @param denominator
* @return A pointer to the fraction structure on heap . (memmory should
be de-allocated manually)
*/
Fraction *fraction_new(int numerator, int denominator)
{
  Fraction *f = NULL;
  if (!denominator) {
    fprintf(stderr, "Invalid fraction. Denominator cannot be 0 (zero).n");
    return (f);
  }
  f = malloc(sizeof(*f));
  if (!f) {
    MALLOC_FAIL;
  }
  f->numerator = numerator;
  f->denominator = denominator;
  return (f);
}

/**
* De-allocates the memory associated with a given fraction .
* @param f The fraction to be free'd .
*/
void fraction_delete(Fraction *f)
{
  if (f) {
    free(f);
  }
}

An important aspect is that the fraction_new() function fails if a 0 (zero) denominator is given .

Step 3:

On this step we will write a function that reduces the fraction to lowest terms . For this we will also need to determine the greatest common divisor of the fraction’s denominator and numerator in order to divide the fraction