Assignment 8, due Oct 22

Always write your name legibly as it appears on your University ID and on the class list!

Homework

1. Background: The classic multiplication algorithm used on early computers took two one-word numbers, call them a and b, and produced a two-word product, call it hl where h is the high word of the product and l is the low word of the product. If the word size is n bits, the algorithm can be expressed as follows:

   h = 0;
   l = b;
   repeat the following n times {
   

   if l is odd thebn h = h + a
   hl = hl >> 1

   }
   now hl = a × b

   The problem: Write a Hawk subroutine to multiply two numbers using the above algorithm. The 32-bit multiplicands are passed in R3 and R4 and the 64-bit product is returned in R3 (the low half) and R4 (the high half). (1 point)

2. Background: The minimal standard pseudorandom number generator is a popular way to generate sequences of numbers that appear to be random. This uses a 32-bit global variable called, seed, an unsigned integer. Each time a new random value is needed, seed is updated using the parameterless subroutine random(). The algorithm is as follows:

   constant a = 16,807
   constant m = 2,147,483,647
   constant q = m / a
   constant r = m % a

   note seed will always be in the range 1 to m-1, inclusive.

   random() is {
   

   seed = a * (seed % q) - r * (seed / q)
   if seed < 0 then seed = seed + m

   }

   a) Write the RANDOM routine for the Hawk, using the multiply and divide routines in the hawk monitor. You will probably need to compute the constants q and r using a calculator. (1 point)

   b) Can you come up with an efficient way to multiply by the constant a using shift and add sequences? (0.5 points)

   c) Can you come up with an efficient way to multiply by the constant r using shift and add sequences? (0.5 points)