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 .

E.g.

Reducing 36 / 120 it becomes 3 / 10.

Implementation

Encapsulating the fraction using a struct{}

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

Creating a constructor()-like and destructor()-like functions

//
// 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);
	}
}

The fraction_new() function fails if a 0 (zero) denominator is supplied.

Reducing the fraction to the lowest terms using the gcd() algorithm

On this step we will write a function that reduces the fraction to the 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 .

//
// Calculates the greatest common divisor.
// @param num1
// @param num2
// @return GCD
//
int util_gcd(int num1, int num2)
{
	int tmp;
	num1 = abs(num1);
	num2 = abs(num2);
	while (num1 > 0) {
		tmp = num1;
		num1 = num2 % num1;
		num2 = tmp;
	}
	return num2;
}

//
// Reduce a fraction to the lowest terms
// @param f The fraction to be reduced .
//
void fraction_reduce(Fraction *f)
{
	int gcd;
	gcd = util_gcd(f->numerator, f->denominator);
	f->numerator /= gcd;
	f->denominator /= gcd;
}

Main method

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

int main(int argc, char *argv[])
{
	Fraction *f = NULL;
	f = fraction_new(36,120);

	printf("f = %d/%d", f->numerator, f->denominator);
	fraction_reduce(f);

	printf(" = %d/%dn", f->numerator, f->denominator);

	fraction_delete(f);
	return (EXIT_SUCCESS);
}

Output:

f = 36/120= 3/10

Full source-code:

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

#define MALLOC_FAIL abort()

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

int util_gcd(int num1, int num2);
Fraction *fraction_new(int numerator, int denominator);
void fraction_delete(Fraction *f);
void fraction_reduce(Fraction *f);

//
// 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);
	}
}

//
// Calculates the greatest common divisor.
// @param num1
// @param num2
// @return GCD
//
int util_gcd(int num1, int num2)
{
	int tmp;
	num1 = abs(num1);
	num2 = abs(num2);
	while (num1 > 0) {
		tmp = num1;
		num1 = num2 % num1;
		num2 = tmp;
	}
	return num2;
}

//
// Reduce a fraction to the lowest terms
// @param f The fraction to be reduced .
//
void fraction_reduce(Fraction *f)
{
	int gcd;
	gcd = util_gcd(f->numerator, f->denominator);
	f->numerator /= gcd;
	f->denominator /= gcd;
}

int main(int argc, char *argv[])
{
	Fraction *f = NULL;
	f = fraction_new(36,120);

	printf("f = %d/%d", f->numerator, f->denominator);
	fraction_reduce(f);

	printf(" = %d/%dn", f->numerator, f->denominator);

	fraction_delete(f);
	return (EXIT_SUCCESS);
}

Note: As an alternative to Euclid’s Algorithm take a look on Stein’s Algorithm.