MIPS - Euclidean Algorithm The Euclidean Algorithm (60 Points) CS 281 Systems Architecture I Overview This part of the assignment consists of writing two MIPS assembly language programs and testing them using the MIPS simulator SPIM. Students will implement two versions (iterative and recursive) of the Euclidean algorithm that compute greatest common divisor for two integers. The SPIM simulator is described in appendix A and can be obtained from http://www.cs.wisc.edu/~larus/spim.html (or for the PC version locally at pcspim.zip). Lab 3 provided an introduction to the use of SPIM. Description Students will implement two versions (iterative and recursive) of the Euclidean algorithm that computes the greatest common divisor (GCD). The algorithm is over 2000 years old and is used in computer algebra applications such as cryptography. The algorithm is based on the facts that for two integers a and b (not both zero), gcd(a, b) = gcd(a+kb, b) for any integer k as well as gcd(a, b) = gcd(b, a mod b). Please see Euclidean Algorithm.pdf for more detailed description of the algorithm as well as proof of correctness for the algorithm. What to do Review the sample C++ code: euclidean_iterative.cpp and euclidean_recursive.cpp. You should generally follow the C++ code while writing your MIPS code. Iterative Euclidean Algorithm: Write an iterative version of the algorithm. Use syscall for cout and cin. Use rem pseudoinstruction for mod operation. Make sure you follow all MIPS procedure calling conventions. Recursive Euclidean Algorithm: Write a recursive version of the algorithm. Use syscall for cout and cin. Use rem pseudoinstruction for mod operation. Make sure you follow all MIPS procedure calling conventions. Run and test your programs in SPIM. There must be a reasonable output to the console. Please review Lab 4 for more information and help. Do not combine the two programs: submit two separate files, even though mains will be the same. Note: graders are instructed to take at least 25% off your grade if your program does not work as expected. What to hand in A separate description file (5 points) should summarize what you did: summarize code you wrote, experiments performed, and files included, etc. Please follow my specifications for a description file. Documented MIPS source code for both iterative (30 points) and recursive programs (25 points). Please follow the specifications above and in the C++ code provided. Each function must have input and output specifications. A copy of the console output from executing both of your main programs -- use PrintScreen and paste these screen snapshots into your description file.
