CMPSC 465, Spr 2013
Programming Assignment 1
Empirical Analysis of the Euclidean Algorithm

  1. 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.
  2. 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!
  3. 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!
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.