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

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

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 by it .

Step 4:

The last step will be to test our function . The main function is:

And the output:

Full source-code:

3 thoughts to “Euclid’s Algorithm: Reducing fraction to lowest terms”

1. Arjun Bharadwaj says:

Nicely documented and easy to follow. Thanks! 🙂

1. Arjun Bharadwaj says:

Also I think that the second line of this post, Fraction = Reduce(Fraction) = 3 / 12 should be 3/10 not 3/12.