Difficulty: ★ ★ ★ ☆

Recently, I wrote code to calculate odds. The program’s output listed the odds as a fraction, such as 1/6 for rolling a specific number on a die. But occasionally, the output is something like 7/21. As a human, and after a modicum of mental sweat, I recognize 7/21 as 1/3. The challenge is how to get the computer to recognize and report the smaller fraction.

The mathematical term for changing 7/21 into 1/3 is simplifying a fraction. The value doesn’t change, but ratio is easier to see. Any fraction can be simplified, providing that both the numerator and denominator have common factors other than one.

First, some vocabulary:

numerator

The value at the top of the faction. In 1/3, 1 is the numerator.

denominator

The value at the bottom of the fraction. In 1/3, 3 is the denominator.

factor

A number that divides evenly into another number: 2 is a factor of 8.

Second, as you’ve forgotten from grammar school, the method for simplifying a faction involves these steps:

1. Discover the common factors for the numerator and the denominator.
2. Obtain the largest common factor shared by both numerator and denominator.
3. Divide both the numerator and denominator by their largest, shared common factor.

Of course, Step 3 is really the only step you need, to find the greatest common denominator (GCD). For programming purposes, the other two are important initial steps.

Your challenge for this month’s Exercise is to write code that simplifies a series of fractions. Sample code is provided below that lists numerators and denominators for several fractions; translating decimal values into fractions is a challenge for another day.

2022_03_01-Lesson.c

#include <stdio.h>

int main()
{
    const int size = 7;
    int numerator[size] = { 28, 13, 14, 1, 9, 276, 4 };
    int denominator[size] = { 42, 52, 91, 50, 15, 23, 100 };
    int x;

    for( x=0; x<size; x++ )
    {
        /* output the original fraction */
        printf("%d/%d\n",numerator[x],denominator[x]);
    }

    return(0);
}

Use the skeleton above to craft your Exercise solution. It presents seven fractions, separating the numerator and denominator into arrays. Here is the output:

28/42
13/52
14/91
1/50
9/15
276/23
4/100

I have devised two solutions for this Exercise. The first plods through the steps shown earlier to locate common factors, find the largest shared factor, then divide the numerator and denominator by the largest common factor (GCD).

My second solution uses the Euclidean algorithm to simplify the fractions. The linked Wikipedia page uses pseudo code to demonstrate the algorithm. If you go this route, please write your own code instead of cribbing from the pseudo code.

By the way, my Euclidean algorithm solution takes 50 fewer lines of code to implement.

You may do one solution or both. You can review my solutions here, but please try this Exercise on your own before you do.