EXAMPLE—FINDING THE GREATEST COMMON DENOMINATOR

In mathematics, a famously successful and useful algorithm is Euclid’s algorithm for finding the greatest
common divisor (GCD) of two numbers. The GCD is the largest integer that will evenly divide the two numbers
in question. Euclid described his algorithm about 300 BCE.
Without having Euclid’s algorithm, how would one find the GCD of 372 and 84? One would have to factor
the two numbers, and find the largest common factor. As the numbers in question become larger and larger,
the factoring task becomes more and more difficult and time-consuming. Euclid discovered an algorithm that
systematically and quickly reduces the size of the problem by replacing the original pair of numbers by smaller
pairs until one of the pair becomes zero, at which point the GCD is the other number of the pair (the GCD
of any number and 0 is that number).
Here is Euclid’s algorithm for finding the GCD of any two numbers A and B.
Repeat:
If B is zero, the GCD is A.
Otherwise:
find the remainder R when dividing A by B
replace the value of A with the value of B
replace the value of B with the value of R
For example, to find the GCD of 372 and 84, which we will show as:
GCD(372, 84)
Find GCD(84, 36) because 372/84 —> remainder 36
Find GCD(36, 12) because 84/36 —> remainder 12
Find GCD(12, 0) because 36/12 —> remainder 0; Solved! GCD = 12
More formally, an algorithm is a sequence of computations that operates on some set of inputs and produces
a result in a finite period of time. In the example of the algorithm for designing stairs, the inputs are the total rise
and total run. The result is the best specification for the number of steps, and for the rise and run of each step.
In the example of finding the GCD of two numbers, the inputs are the two numbers, and the result is the GCD.
Often there are several ways to solve a class of problems, several algorithms that will get the job done. The
question then is which algorithm is best? In the case of algorithms for computing, computer scientists have
developed techniques for analyzing the performance and judging the relative quality of different algorithms.