Algorithmics - The Computing Universe: A Journey through a Revolution - page 85

Knuth ( B.5.2 ) and David Harel ( B.5.3 ). When the steps to define an algorithm
to carry out a particular task have been identified, the programmer chooses a
programming language to express the algorithm in a form that the computer
can understand.

The earliest known algorithm was invented between 400 and 300 B.C. by
the Greek mathematician Euclid. Euclid's algorithm is a method for finding
the greatest common divisor, or GCD, of two positive integers. For example, the
fraction 8/12 can be reduced to 2/3 by dividing both numerator and denomina-
tor by their GCD, which in this case is 4. The algorithm to find the GCD of two
numbers, M and N, can be expressed in four steps (see Fig. 5.2 ):

Step 1: Input values M, N.
Step 2: Divide M by N to find the remainder R.
Step 3: If R is zero then N is the answer, print N.
Step 4: If R is not zero, change the value of M to N and the value of N to R
and go back to Step 2.

Fig. 5.1. A page from al-Khowarizmi's
topic on algebra. In this topic he
describes the steps for solving linear
and quadratic equations and lays down
the foundations of algebra as a new
discipline of mathematics. The original
meaning of the word algebra in Arabic
is “to restore” - this refers to balancing
out both sides of an equation. It is hard
to overstate the importance of algebra in
mathematics.

How does this algorithm work? Any number that divides both M and N must
also divide the remainder R. Similarly, any number that divides both N and R
must also divide M. This means that the GCD of M and N is the same as the
GCD of N and R. We can see the algorithm in action in Table 5.1 for finding
the GCD of 65 and 39. We begin by dividing 65 by 39 - we are interested only
in the remainder, which is 26. We assign M the value of 39 and N the value of
the remainder 26. In the next iteration we calculate the remainder again and
assign values to M and N. We repeat the process until the remainder becomes
zero, in this case the value of GCD will be held in variable N.
As Harel says in the title of his topic, algorithms can be regarded as the
“spirit of computing.” They are the precise procedures required to get computers
to do something useful. In this chapter we will look at some examples of differ-
ent types of algorithms. Historically, computers were used to solve numerical
problems so we will start by looking at algorithms for numerical simulations.
We will also introduce the idea of using random numbers to derive approximate
answers to complex simulations. These “Monte Carlo” methods were first used in
the Manhattan atomic bomb project. We will then look at problems such as find-
ing the quickest way to sort a list of names and finding the shortest path from
one city to another - as we now do routinely with our global positioning system,
or GPS, navigation systems. This will lead us to a discussion of the efficiency of
algorithms and an introduction to computational complexity theory.

Fig. 5.2. Flowchart of the GCD algo-
rithm. The “%” operation calculates the
remainder when M is divided by N.

Input M, N

Table 5.1. Euclid's algorithm for
GCD of 65 and 39
M

R = M%N

N R

Iteration 1 65 39 26

yes

R = O

Iteration 2 39 26 13

no

Iteration 3 26 13 0

M = N
N = R

print N

Result GCD = 13