C# Greatest Common Denominator
Euclidean Algorithm
Greatest Common Denominator
The greatest common denominator, or GCD, between two numbers is the greatest integer that divides both given numbers. Writing a C# program that can calculate the greatest common denominator (GCD) of large numbers quickily would be very useful.
The first idea that comes to mind is perhaps to write a for loop to check all numbers that are less than the pair of numbers to find the GCD. However there is a more efficient way using the Euclidean Algorithm.
Euclidean Algorithm
The Euclidean Algorithm is pretty straight forward: given two numbers, repeatedly replace the larger number with the greater number mod the lesser number. Keep repeating the step until one of the two numbers reaches zero, the other number will then be the greatest common denominator (or greatest common divisor), the GCD.
Recursive
The Euclidean Algorithm lends itself to a recursive C# function (a function that calls itself):
public int GCDRecursive(int a, int b) { if (a == 0) return b; if (b == 0) return a; if (a > b) return GCDRecursive(a % b, b); else return GCDRecursive(a, b % a); }
Looking over the code it does exactly what the Euclidean Algorithm describes: repeatedly calls itself until one of the two numbers reaches zero.
Non-Recursive
For a variety of reasons, you might want a C# function that is non-recursive. It is not as elegant or simple to understand, but it can be written:
public int GCD(int a, int b) { while (a != 0 && b != 0) { if (a > b) a %= b; else b %= a; } if (a == 0) return b; else return a; }
Speed
One reason for using the non-recursive Euclidean Algorithm function over the recursive one to find the greatest common denominator is for speed. .NET functions that call themselves suffer a slight performance impact. For example, some rough tests using the SpeedTester C# Class showed a 34% increase in speed by using the non-recursive GCD function.