CS 61C (Fall 2007)

Quiz 10

Two questions, submit as "quiz10".  Due 2:45pm before lecture 9/21/2007.


1.

Suppose that the variable "sp" in a C program represented the stack pointer for the system stack. On the MIPS architecture, which of the following represents the popping of one element off the stack?
  1. poppedElement = *(sp++)
  2. poppedElement = *(sp--)
  3. poppedElement = *(++sp)
  4. poppedElement = *(--sp)

 

2.

Recall Euclid's algorithm for computing the greatest common divisor: gcd (a, b) = a if b == 0, otherwise gcd (b, a%b)

Consider the following assembly language code, part of an implementation of this algorithm. 

gcd:    ...                             # push some information onto the stack
        bnez    $a1,recursive_case      # if b == 0 ...
        move    $v0,$a0                 # gcd = a
        j       return
recursive_case:
        rem     $t0,$a0,$a1             # $t0 = a%b
        move    $a0,$a1                 # gcd = gcd (b, a%b)
        move    $a1,$t0
        jal     gcd
return: ...                             # pop the stack and return

How many words should gcd push onto the stack each time it is called?  Why?