Homework 9

22C:122, Fall 1998

Due Monday Nov 2, 1998, in class

1. Write (pseudo)code to computer the reciprocal of an unsigned integer i on a binary computer; assume that the multiply instruction on this computer produces a product of length 2N bits, and that both the integer i and the reciprocal of the integer i occupy exactly N bits.

   You can test your code, if you write it in C and then try to do division using the following code:

   #define div(a,b) ( (a * recip(b)) >> N )
   

2. Look up the MARK instruction on the DEC PDP-11 computer. There are large numbers of reference books that describe this instruction in the library, and there are many web resources describing this instruction. From the documentation you can find, what is the purpose of this instruction?

   By way of summary, are some definitions:

   JSR R, DST
      M[--SP] = R
      R = PC
      PC = DST
   

   Note that because PC is a register, it is legal to write JSR PC, DST to do the naive call where the return address is pushed on the stack.

   RTS R
      PC = R
      R = M[SP++]
   

   Again, note that RTS PC is the naive call that pops the stack into the program counter.

   MARK N
      SP = PC + (2 * N)
      PC = R5
      R5 = M[SP++]
   

   To understand the above, note that the most common register to use for a JSR instruction (other than the naive use of JSR PC) is R5. Thus, the final two lines above match the normal RTS. The mystery is, how can you use this strange instruciton to make a useful stack mark!

3. Consider the problem of implementing recursive functions on a machine like the IBM system 360 or the Hawk machine, where the call instruction simply places the return address in a register and where the hardware designates no register as the stack pointer. What is an appropriate calling sequence, receiving sequence and return sequence for use on such a machine.