G12FCO -- Formal Computation

Lecture 1 -- Algorithms

Let us start with a problem. What is the HCF [highest common factor, same as GCD or greatest common divisor] of 1193619 and 2496396?

...pause...

Suppose I tell you it's 21. Do you believe me? You can easily verify that 21 is a factor of both these numbers, how can we tell whether or not there are larger common factors?

...pause...

For this we need a process or algorithm for finding HCFs. You may already know one such algorithm; it consists of finding all the prime factors of the numbers concerned, then you can list all the common prime factors, and `obviously' the HCF is the product of these. But finding prime factors is a rather time-consuming operation for large numbers; doing it efficiently needs very complicated computer programs, and still takes forever and a day when the numbers are large enough to be of cryptographic interest [but that's another story]. So, we look instead at a process known as Euclid's algorithm. This works as follows:

Divide 2496396 by 1193619. The result is 2, with remainder 109158. In other words, 2496396 = 2 × 1193619 + 109158. What has this gained us? Two things:

It is easy to see from this equation that any number which divides both 2496396 and 1193619 also divides both 1193619 and 109158, and vice versa. So, the set of divisors of either pair is the same as the set of divisors of the other pair, and in particular, the greatest common divisor is the same. [But note that common divisors of 2496396 and 109158, such as 2, do not necessarily divide 1193619, because of the quotient.] We have found another pair of numbers with the same HCF.
109158 is simpler than 2496396.
So, instead of finding the HCF of 2496396 and 1193619, we can instead find that of 1193619 and 109158; the answer will be the same, and the problem is easier because the numbers are smaller. How do we find the new HCF? Why, by the same method, of course; divide 1193619 by 109158, find the remainder and set up an even easier problem. Keep going until the answer is obvious.

What do I mean by the answer being `obvious'? Let's continue this process and see:

	Divide 2496396 by 1193619;  quotient 2 remainder 109158.
	Divide 1193619 by 109158;  quotient 10 remainder 102039.
	Divide 109158 by 102039;  quotient 1 remainder 7119.
	Divide 102039 by 7119;  quotient 14 remainder 2373.
	Divide 7119 by 2373;  quotient 3 remainder 0.
	Divide 2373 by 0;  oops!

We can't divide by zero, but luckily the HCF of 2373 and 0 is `obviously' 2373, so the answer is 2373 [and I lied -- note that 2373 = 21 × 113]. In summary, the process is:

To find the HCF of two non-negative integers, replace the larger by the remainder when it is divided by the smaller. Repeat until the smaller number is zero, at which stage the answer is the other number.

Turning this process into a computer program is left as an exercise. [Note that after the first division, you always know which is the smaller number, and before it doesn't matter except for wasting the first division; note also that you should test for zero before doing the division!] There are many variants of this technique: one is to replace division by subtraction, which is easier to analyse and program but gets very slow if the quotient is large; another uses binary shifts and subtractions, which can be made very efficient in computer machine codes but is harder to explain.

Algorithms

An algorithm is a process with three properties [and we'll discuss in a later lecture what we can do with processes that may be useful but that don't have these properties]:

It must be deterministic, so that anyone can follow the same process on the same example and verify that they get the same result.
The process must terminate, so that we actually do get a result.
The process must be correct, so that the result we get is the right one.

Determinism is usually assured by describing the process in terms of a computer program, either a real program in a real language [such as QBasic or Maple] for a real computer, or as a pseudo-program in an informal language that looks rather like a computer language for an idealised computer. The latter is not mere idleness; if you try to write real programs, you tend to get bogged down in details of declaring variables, formatting the output, and so on, that may be important but that don't help the reader to understand what the process is really doing. Note that the use of `random' numbers is not allowed.

Termination is only a problem if the program has uncounted loops [using while or until rather than for, in QBasic terms] or recursive procedures [that call themselves]. Showing that the program terminates is then usually akin to mathematical induction; there is an inductive step [`this instance terminates because all simpler instances terminate'], and a base case [`this really simple instance terminates'].

In the HCF example, the remainder is always strictly smaller than the quotient, so the sequence of remainders is a sequence of strictly decreasing non-negative integers, which must therefore eventually reach zero, at which point the process stops. Note that the same sorts of pitfalls can arise here as can arise in other parts of mathematics. For example, decreasing sequences of non-negative real numbers don't necessarily reach zero, or even tend to zero [1.1, 1.01, 1.001, ...]; the decrease must be strict [5, 3, 2, 2, 2, ...]; and integers can decrease indefinitely [9, 7, 5, 3, 1, -1, -3, ...].

Proving correctness of a program is, perhaps, a new concept to you! Of course, we can't prove that you haven't made a typing error in the program, nor that the computer has correctly executed the program we told it to execute, nor that the proof we construct is correct [for that would require a proof that the proof that the constructed proof is correct is correct, which would require a proof that ..., which route leads to madness and an infinite regress]; we defend against these errors as best we can by running test cases and by the usual rather ad hoc debugging techniques. But there are things that can be done. The most usual ideas are invariance, guards and post-conditions, together with mathematical notions such as induction.

In the HCF example, the whole essence of the process was that the HCF was preserved unchanged through the remaindering sequence; this is a typical example of invariance [like `energy conservation' in mechanics -- you don't know what's happening in the middle, but you at least know that you come out with what you started with]. We'll see other, rather woollier, examples later. Guards are things like testing to see if something is positive before taking its square root; within the statement covered by the test, you can rely on the thing being positive, which presumably helps the mathematics. Post-conditions are things like having loops of form while remainder <> 0 ... ; immediately after that loop, you know that remainder is zero; combining this with the invariant in the HCF example, this is how we know that the HCF we really want is the same as the HCF of two numbers of which one is zero -- the nice simple case that we can solve immediately.

A final point, to flog the HCF example to death. A perfectly good algorithm for the original problem would be, in essence,

print "The HCF of 1193619 and 2496396 is 2373"

This is clearly deterministic and terminating; but how could you satisfy yourself of its correctness? It is correct, but to be sure of that you would have to write a more general HCF finder, and plug these numbers into it. So this algorithm is useless; you might just as well write a more general algorithm in the first place. This is a characteristic of over-specified problems. We shall return to this theme later in the module. For now, let us just note that it is not only more æsthetically satisfying to find general results, it also leads to better algorithms, which are easier to analyse.

top of page

G12FCO home page. border=0

Next lecture. border=0

Problem class 1.