Procedure solver
Can you think like a computer and work out what this flow diagram
does?
Image
Can you prove that the algorithm will always work?
NOTES AND BACKGROUND
When computers do their various jobs they follow very clearly described procedures. These are series of instructions where the next step at each stage is 100% clearly described: no choices or decisions need to be made; the computer is told exactly what to do. The art of the computer programmer is to work out how to break down a task into such a series of steps so that the computer knows exactly how to perform that task.
The procedure in this question is an example of such a breakdown. The computer user would input the two numbers X and Y and the computer would then run through the procedure until it terminates.
Thinking in this procedural way is an important skill to develop for anyone wishing to learn how to program a computer (and perhaps to earn a great deal of money!).
You will need to experiment with various choices of number. A clear
recording system will be necessary.
Chanwc from Hong Kong, Matthew from QEB, Alpha Lee from Yew Chung International School, Phil from Garforth Community College and Andrei from Tudor Vianu National College all correctly worked out that the algorithm produces the greatest common factor of two whole numbers .
Aneesh correctly applied the algorithm for the cases X = 4 and Y = 1 and conjectured that the algorithm was to produce the output 1, whereas Alpha started with this example:
initial x_i = 25 y_i = 5
1. x_1 = 25-5 = 20 y_1 = 5 since x_i> y_i
2. x_2 = 20-5 =15 y_2 = 5 since x_1> y_1
3. x_3 = 15-5 =10 y_3 = 5 since x_2> y_2
4. x_4 =10-5 =5 y_4 = 5 since x_2> y_2
5. x = output = 5 since x_4 = y_4 gcd(25,5) = 5 since 25 = 5*5 5 = 5*1
The algorithm (which was discovered by the Greek mathematician Euclid over 2000 years ago) makes use of the fact that the greatest common divisor of two numbers (a ,b) equals the greatest common divisor of (a, b-a). Andre, Alpha and Phil all noticed this fact, giving good, clear proofs. Phil's notation was particularly clear :
Rename the two integers X and Y as AH and BH, meaning 'A multiples of the HCF' and 'B multiples of the HCF'. The difference between them, AH-BH, factorises to H(A-B). The difference between integers X and Y must be an integer, as must the difference between A and B, so the difference between X and Y must be a multiple of the HCF. Phil then noted that As the algorithm cycles, the numbers X and Y will always be replaced with lower multiples of the HCF of the original X and Y. The algorithm continues to subtract until only the HCF remains.
Matthew from QEB also solved the problem and, interestingly, converted the procedure into Javascript, a programming language most commonly used in webpages :
function getHCF(x,y) {
while (x != y) {
if (x > y) { x = x-y }
if (x < y) { y = y-x }
}
return x;
}
Matthew gave a clear and extended description of his code, which you can read about here .This is recommended for any budding programmers!
Why do this problem?
This problem is an introduction to algorithmic thinking. This branch of mathematical activity is of great use in decision mathematics and leads students into the important art of computer programming. It is essentially content free in terms of prior knowledge, so may be used at any stage of a course of study.Possible approach
This problem should be shown to the students with no
explanation. What sense can they make of the layout and the
problem? Gradually the concept that the problem represents an
algorithm will emerge. Students may then begin to test the
algorithm on pairs of numbers to try to determine what the
procedure does. Can they prove that the algorithm does this in
general?
Students might want to think algebraically. They might become
confused by the assigments `X = X - Y' and will need to understand
that X represents a 'place holder' for a value which can change at
each step of the procedure. Whilst such reassignements are common
in computer programming, they might be seen as unusual by sixth
formers.
Key questions
This question demands clear organised thinking. Questioning
should encourage this.
- What do the arrows and boxes represent?
- What happens, for example, for X = 10; Y = 25?
- What is the meaning of an expression such as 'X = X - Y'?
Possible extension
- Can you program this procedure into Microsoft Excel?
- Can you create a clear, step-by-step algorithm to find the solution of a quadratic equation, taking into account that there might be 0, 1 or 2 distinct solutions?
- Pursue more formal ideas of logical programming using our LOGO environment .