CMPSC 465, Spr 2013

Programming Assignment 1

Empirical Analysis of the Euclidean Algorithm

**Using Visual Studio C++, code and test the Euclidean algorithm (on p. 4 of the text) for calculating***gcd*(*m*,*n*), where*m*and*n*are non-negative integers, not both equal to zero.

**Using a global counter, determine the average number of divisions performed by the Euclidean Algorithm for all pairs of integers 1 <=***m, n*< 8 *. (Note that these are integers with at most 3 bits.) Also, use a global variable (or variables) to remember what pair of integers required the most divisions and how many divisions this was. Check your results by hand!**Repeat step 2 for all integers 1 <=***m, n*< 16. (Note that these are integers with at most 4 bits.)**Again, check your results by hand!****When you have debugged your code and are satisfied that the results that it produces are correct, run it for integers with at most 3 bits, then 4 bits, ..., and then, finally, 12 bits. Append each of these runs to a comment that follows your source code.****Use Excel to create a table with 5 columns. The first column will contain the number of bits in***m*and*n*; the second column will contain the average number of divisions performed by the Euclidean Algorithm in computing*gcd*(*m*,*n*); the third and fourth columns will contain the pair of integers that required the most divisions, and the fifth column will be the maximum number of divisions.**Use Excel to create a graph of average divisions performed by Euclid's algorithms as a function of the maximum number of bits in***m*and*n*.**Make****hypotheses about both the worst and average case efficiencies of the Euclidean Algorithm. You may add additional columns to your Excel results to support your hypotheses.****No later than 11:59PM, Tuesday, Jan. 15: Put your C++ code and your Excel spreadsheet(s) into your drop folder at X:\Public\CMPSC 465 Spr 2013\Drop Folders, where X: is your instructor's shared disk.****At the beginning of class on Wednesday, Jan. 16 turn in (a) a signed and dated integrity statement, (b) a hardcopy of your code, with appended runs, (c) your Excel spreadsheet(s), and (d) your hypotheses from step 7. Collate and staple these materials.**

*** 1 <= m, n < 8 means that 1 <= m < 8 and 1 <= n < 8.**