## Euclid’s Algorithm: Reducing fraction to lowest terms

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