Handout 13A

The purpose of this exercise is to write a LOGO procedure that uses the Euclidean Algorithm to determine the greatest common divisor of two numbers.

Sometimes computers need to find the greatest common divisor of a pair of numbers. In a high school course, you might use the GCD to write a fraction in reduced form or in a program to efficiently draw star-shaped polygons. In this exercise we implement a well known algorithm for finding the greatest common divisor. Below is a pseudocode description of the algorithm.

  1. Input :N and :K.
  2. Divide :K into :N to get remainder :R.
  3. If :R=0 output :K and stop.
  4. Replace :N by :K, replace :K by :R, and return to step 2.
Why is the output of this algorithm a divisor of the original arguments :N and :K? (Hint: we can think of doing division with remainder as writing :N = :Q * :K + :R, where we require that 0 <= :R < :K.)

Does this algorithm always reach an answer, or can it get caught in an infinite loop?

Challenge: prove by induction that the output of this algorithm really is the greatest common divisor of :N and :K.

Recall the PQGON procedure from week 5 of the semester: 

TO PQGON :P :Q :SIDE
  REPEAT :Q [FORWARD :SIDE RIGHT (360 * (:P/:Q))]
END
When the fraction :P/:Q is in reduced form the total turtle turn of this procedure is 360 * :P which is the least it could possibly be and still be state transparent. When the fraction :P/:Q is improper the turtle retraces its path. Recall the question:

The answer is that :N must be :Q / (GCD :P :Q), where GCD is a LOGO procedure that outputs the greatest common denominator of two numbers.

Run PQGON or the REPEAT statement above with different values of :N, :P and :Q to convince yourself that this is true. Can you prove that this is true?

Use the Euclidean Algorithm and LOGO's REMAINDER procedure to write a program GCD :N :K that computes the greatest common divisor of two numbers :N and :K.

Use your GCD procedure to write a FASTPQGON procedure that draws the same thing that PQGON does without the turtle's having to retrace its path.

Mtht420