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):

1 2 3 4 5 6 7 8 |
/** * 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 ) .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/** * 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 Read More