Assignment 8, due Mar 29

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: Here is a classic algorithm for computing square roots on a 32-bit computer -- lifted from the Wikipedia article on methods of computing square roots:

   unsigned int sqrt(unsigned int num) {
           short result = 0;
           short bit = 0x40000000; /* 1 << 30, the largest power of 4 */
    
           /* make "bit" the highest power of four <= the argument */
           while (bit > num) bit >>= 2;
    
           /* now compute the square root from this initial value */
           while (bit != 0) {
                   if (num >= result + bit) {
                           num = num - (result + bit);
                           result = (result >> 1) + bit;
                   } else {
                           result = result >> 1;
                   }
                   bit = bit >> 2;
           }
           return result;
   }
   

   This looks a lot like the traditional pencil and paper square root algorithm that my grandfather used to teach his high-school math students but that was no-longer taught by the time I took high-school math in the late 1960s. For an explanation (if you are curious), see the Wikipedia page, but note that you don't need to understand the code in order to do this assignment.

   A problem: Give a translation of this code to Hawk assembly language, as a function that takes one parameter in R3 and returns the result in R3. Paper and pencil will suffice, if your code is correct, but we will be hard-nosed about syntax errors and legibility. Your code must include the original code in the comments, so that we can see what is going on! (1.5 points)

2. Background: Write efficient Hawk code to multiply by each of the following constants. Note that section 14.2 of the Hawk manual solves this exercise for all constants up to 48:

   a) 99 (it can be done in 4 instructions) (0.2 points)

   b) 999 (it can be done in 4 instructions) (0.2 points)

   c) 9999 (this one is harder) (0.4 points)

3. Background: Consider the problem of converting inches to feet. This involves division by 12. In binary,
     1/12 = 0.00010101010101010101010101010101011
   (This is rounded to 32-bits of precision, not counting the leading zeros.)

   Note that section 14.6 of the Hawk manual discusses reciprocal multiplication as a way to do efficient division by constants.

   A problem: Give Hawk code to multiply R3 by 1/12. (0.7 points)