On page 2 of volume 1 of The Art of Computer Programming, Donald Knuth presents the following translation of “Euclid's algorithm” as an example of an algorithm1.
Algorithm E (Euclid’s algorithm). Given two positive integers m and n, find their greatest common divisor, i.e. the largest positive integer which evenly divides both m and n.
E1. [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 ≤ r < n.)
E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
E3. [Interchange.] Set m ← n, n ← r, and go back to step E1. ∎
|_______________________________________ ↓ no | [E1. Find remainder] → (E2. Is it zero?) → [E3. Interchange] ↓ yes
Knuth explains the left arrow symbol used in step E3:
The “←” arrow in step E3 is the all-important replacement operation (sometimes called assignment or substitution); “m ← n” means the value of variable m is to be replaced by the current value of variable n.
C++, C#, Java, JavaScript are a few examples of programming languages that use a single equals sign (=) instead of the left arrow symbol for assignment. To compare two values, these languages often use two equals signs (==) and sometimes even three (===) instead of the single equals sign used in step E2.
Here's another example and an algorithm, à la Knuth, courtesy of yours truly (see also MR Algoreisms):
MR0. [Assert Inputs]: Assert n and m are integers and m is not zero. If the assertion is false, raise an error and do not continue; the algorithm must terminate. ∎
MR1. [Remove Sign]: Set n ← |n|, m ← |m|. (We will have n ≥ 0 and m > 0.)
MR2. [Reduce]: Set n ← n – m.
MR3. [Positive?]: If n > 0, go back to step MR2.
MR4. [Remainder?]: (We will have n ≤ 0.) If n equals zero, there is no remainder (i.e. the answer is zero); otherwise, n + m is the answer. Return the answer; the algorithm terminates. ∎
↓
(0. Assert Inputs) → error
| ok ______________
↓ ↓ yes | no no
[1. Remove Sign] → [2. Reduce] → (3. Positive?) → (4. Remainder?) →
↓ yes
Now that we've looked at a couple of examples of algorithms, let's consider the question, "What is an algorithm?" Knuth says:
The modern meaning for algorithm is quite similar to that of a recipe, process, method, technique, procedure, routine, except that the word “algorithm” connotes something just a little different. Besides merely being a finite set of rules which gives a sequence of operations for solving a specific type of problem, an algorithm has five important features:
1) Finiteness. An algorithm must always terminate after a finite number of steps. . . .
2) Definiteness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case. . . .
3) Input. An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins. . . .
4) Output. An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs. . . .
5) Effectiveness. An algorithm is also generally expected to be effective. This means that all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a [person] using a pencil and paper.
__________________________________
| no ↓
(14. Tired?) → [15. Sleep] → [7. Begin new section]
yes
Notes
- not to be confused with AlGore-rhythm
