Math 304 ML: Euclidean algorithm

Due Friday, February 11, in your Blackboard drop box

Write code that implements the Euclidean algorithm. In particular, note the code for ggcd in PSML (not gcd--you will need the fuller version in the next assignment). Expand this code so it also counts the number of steps in the algorithm. Probably the best way is to turn ggcd into, say, ggcdhelp (m,n,count) that does the recursive (iterative) step and increments count by 1. Then let (say)

gcd m n = ggcdhelp (m, n, 0);

Test your code with the following problems:

p. 60, #1, 6, 12, 13
p. 69, #6, 7

A run should look something like:

gcd 20 3 = (1,~1,7,3),

where 1 is the gcd, ~1 (minus) and 7 are the coefficients and 3 is the number of steps.

The step count in the book might be one off from yours--it depends on where you start counting. Don't worry about it.

Note that the discussion on this section of PSML concerns "verifiable code." That is, the code "checks itself," essentially by substituting the answer it gets back into the problem. This is an important concept in modern computer science.

10 points (not easy) extra credit: code the Chinese remainder theorem (page 82). The input will be a list

[(a₁,n₁),(a₂,n₂),...,(a_r,n_r)],

and the output will be X.

Do it first for r=2, using the Euclidean algorithm. Then note that the general case can be done recursively.