In previous articles, I’ve talked about the importance of finding the right algorithm, or series of steps to follow, when coding a solution. Efficiency in terms of the amount of memory used and the amount of time taken by the operation are key factors for the program. Sometimes an appropriate algorithm is already available and in wide use and it’s just up to the programmer to turn it into code. There’s always the option of running to StackOverflow and grabbing some code but that does nothing to further your talent.

In this example, I want to talk about one of the oldest algorithms known and that’s Euclid’s Algorithm for determining the highest common number by which two other numbers can be divided, also called the Greatest Common Denominator (GCD).  You can see the full details on the Wikipedia link above but the steps come down to this:

1. Divide the smaller number into the larger one and get the remainder (i.e. 450 / 100 = 4 with a remainder of 50)
2. Repeat Step 1 with the smaller of the two numbers and the remainder (i.e. 100 / 50 = 2 with no remainder)
3. Repeat the first two steps until you get a remainder that divides into both of the original numbers without leaving a remainder of its own. That’s the GCD. In this example, that’s 50 which is the GCD for 450 and 100.

To see another example, let’s try 960 and 500:

960 / 500 = 1 with a remainder of 460 (or '960 / 500 - 1 R 460')
500 / 460 = 1 R 40
460 / 40 = 11 R 20
40 / 20 = 2 R 0
GCD of 960 and 500 = 20

This is often demonstrated by assigning the two numbers to the sides of a rectangle and then repeatedly dividing that rectangle into squares with sides equal to the smaller number as shown below:

As you can guess, tiling a room would be one of the popular real-life applications for the GCD but whatever you’re using it for, you now need a way to code it.  Often, the best way to start out is just to write the code in the same order of the algorithm’s steps and let it grow. Starting with the initial calculation in C#:

Remainder = (HighNumber % LowNumber);
 if (Remainder != 0) 
   {
     HighNumber = LowNumber;
     LowNumber = Remainder;
   }

Leaving aside the need to declare variables and assign values to them for a moment, the lines above show the remainder being calculated from the high and low numbers using the Mod operator. Then the code needs to evaluate the remainder and decide how to proceed so we start an IF statement  and determine if the remainder equals zero (using the Not Equal To operator).

If the remainder IS greater than zero, the calculation will need to continue so we juggle some figures around. The remainder is now going to be divided into the lower number so the high number (960) is discarded, the low number (500) is moved into its place and the remainder (460) becomes the low number.

Now we need two things – a way to loop this calculation and a way to stop it when it finishes.

 do
 {
   Remainder = (HighNumber % LowNumber);
   if (Remainder != 0)
   {
     HighNumber = LowNumber;
     LowNumber = Remainder;
   }
 }
 while (Remainder != 0);

 Return LowNumber;

The DO … WHILE loop works pretty well here. The condition assigned to the WHILE statement tests to see if the remainder is 0. If not, execution is sent back to the top and the remainder is re-calculated with the next pair of values. Otherwise, the program exits the loop and returns the LowNumber value which serves as the GCD.

The variable names imply that there is some way to assign the high and low numbers to the right variables and you could do this manually in the program or by constraints in whatever user interface you program.  You should also test for or prevent 0 from being entered for either of the values. Either way, this code can fit neatly in its own little function as shown below.

private int GCDSolve(int HighNumber, int LowNumber)
{
   int Remainder;
   do
   {
     Remainder = (HighNumber % LowNumber);
     if (Remainder != 0)
     {
       HighNumber = LowNumber;
       LowNumber = Remainder;
     }
   }
   while (Remainder != 0);
   
   return LowNumber;
}