by Zoran Horvat

Dec 12, 2013

Given two integers n >= 0 and m > 0, write a function which reduces fraction n/m by producing a pair of relatively prime numbers p and q such that n/m=p/q.

Example: Suppose that initial fraction is 247/26. Reduced fraction is 19/2.

To reduce a fraction, we need to find a number which divides without remainder both the numerator and the denominator. Larger the divisor, smaller the numerator and the denominator will be after being divided by it. The largest divisor for two numbers is called greatest common divisor (or greatest common factor). When two numbers are divided by their GCD, they become relatively prime. This means that there is no common factor for the two numbers anymore.

So the problem of reducing a fraction is to calculate greatest common divisor of its numerator and denominator k, such that n=pk and m=qk. After dividing both numbers in fraction n/m with k, we obtain the reduced fraction p/q.

Now we will focus on the problem of calculating GCD for two integer numbers n and m. First of all, notice that GCD(n, m) is the same as GCD(m, n). Consequently, we are free to assume that n >= m (if it is not, then we can simply swap the values). Next, we will assume that there is some value k >= 1 such that it divides both n and m: n=pk, m=qk. Finally, we will notice that if k divides n and m, then k also divides their difference n-m. This is proven easily:

We can follow the same logic and claim that k also divides n-2m, n-3m, ..., n-am. This process ends with value a such that n-am becomes smaller than m. In other words, n-am is the remainder after dividing n by m:

By combing this equation with relations to GCD we can prove what we have already predicted: that remainder when dividing n by m shares the same GCD with original numbers n and m:

Since n mod m is less than both n and m, it seems that we have transformed the original problem into a smaller one which yields the same result. We are free to repeat the step and to produce another pair of even smaller numbers. The question is when does this process end? Well, at some point the modulo will eventually have to become zero. At that point we will observe that GCD(x, 0) = x for any positive integer x. This gives us the ending criterion: the process of replacing the lower argument to GCD with modulo result ends when modulo becomes zero. At that moment the other argument, which is still positive, becomes the overall result, i.e. it is the requested GCD(n, m).

Here is the simple recursive solution to the problem:

```
int gcdRecursive(n, m)
{
if (n < m)
return gcdRecursive(m, n);
if (m == 0)
return n;
return gcdRecursive(m, n % m);
}
```

The first if statement ensures that first argument is greater or equal to the second argument, which is prerequisite to calculate the first modulo. Second if statement tests the ending criterion: if smaller argument has reached zero, then the first argument is overall result. Finally, if both arguments are positive, with first argument being greater or equal to the second argument, then we repeat the calculation on modified arguments: smaller number becomes the first argument, and result of modulo operation becomes the second argument.

Function presented above is quite handy, but needlessly complicated in terms of recursive calls. It can be easily transformed into iterative form:

```
int gcd(n, m)
{
if (n < m)
{
int tmp = n;
n = m;
m = tmp;
}
while (m > 0)
{
int tmp = n % m;
n = m;
m = tmp;
}
return n;
}
```

This implementation produces the same output as the recursive one. This function can then be used to reduce the fraction:

```
void reduceFraction(n in/out, m in/out)
{
int k = gcd(n, m);
n /= k;
m /= k;
}
```

Below is the complete implementation of console application in C# which inputs fractions, reduces them and prints them out reduced.

```
using System;
namespace ReducingFractions
{
public class Program
{
static int Gcd(int n, int m)
{
if (n < m)
{
int tmp = n;
n = m;
m = tmp;
}
while (m > 0)
{
int tmp = n % m;
n = m;
m = tmp;
}
return n;
}
static void ReduceFraction(ref int n, ref int m)
{
int k = Gcd(n, m);
n = k;
m = k;
}
static void Main(string[] args)
{
while (true)
{
Console.Write("Enter numerator (negative to exit): ");
int n = int.Parse(Console.ReadLine());
if (n < 0)
break;
Console.Write("Enter denominator: ");
int m = int.Parse(Console.ReadLine());
int p = n;
int q = m;
ReduceFraction(ref p, ref q);
Console.WriteLine("{0} / {1} = {2} / {3}", n, m, p, q);
Console.WriteLine();
}
}
}
}
```

When application is run, it produces output like this:

```
Enter numerator (negative to exit): 12
Enter denominator: 16
12 / 16 = 3 / 4
Enter numerator (negative to exit): 3
Enter denominator: 5
3 / 5 = 3 / 5
Enter numerator (negative to exit): 247
Enter denominator: 26
247 / 26 = 19 / 2
Enter numerator (negative to exit): 0
Enter denominator: 9
0 / 9 = 0 / 1
Enter numerator (negative to exit): -1
```

If you wish to learn more, please watch my latest video course

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- Substituting the Builder with the Sequence of Factory Methods
- Custom Implementation of the Option/Maybe Type in C#
- Pros and Cons of Multiple Constructors
- Defensive Design: An Experiment
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design