Assignment 8, due Jul 10

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 (Tuesday or Thursday). 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: Compare the code of the TIMESU routine in the Hawk monitor with the different versions of the MULTIPLY routine given in the first third of Chapter 9.

   a) Which of the MULTIPLY routines from the notes is most similar to TIMESU? (0.3 points)

   b) What difference is there, if any, between TIMESU and the most similar version of MULTIPLY? Ignore cosmetic differences such as labels, indenting, or comment text. (0.4 points)

   c) What is the benefit of this difference, if any? (0.3 points)

2. Background: The Hawk shift instructions allow you to write machine code equivalent to the C (or Python or Java) expression x << c for small constant values of c. There is no simpe machine instruction on the Hawk to do x << y for arbitrary variable values of y. If C only allowed constant shift counts, you could write a subroutine like this to solve the general case:

   int leftshift( int a, int b ) {
           while (b > 0) {
   		a = a << 1;
   		b = b - 1;
   	}
           return a;
   }
   

   The above subroutine is far from optimal. Consider a call to leftshift(x,1000) on a computer with a 32-bit word. After the first 32 iterations, a will not change, yet the loop will continue for hundreds of additional useless iterations.

   Computer scientists are well known for looking for logarithmic-time solutions instead of linear ones. The above code is linear, the time taken to shift n bits is proportional to n. A logarithmic-time solution can be written that tests each bit of the shift count b, shifting a one place if b is odd, two places if the next bit is set, three places if the next bit, and so on.

   a) Translate the C code given above into well commented SMAL Hawk code. Note that you should be able to solve this with just 6 machine instructions. (1 point)

   b) Write SMAL Hawk code for a logarithmic-time solution. Ignore the problem of shift counts greater than 31. Note that this can be solved with only 16 instructions, a return instruction plus 5 groups of 3 instructions, one group per bit of the shift count. (1 point)