1. [50pts] Convert the following recursive Greatest-Common-Factor function into MIPS assembly language.

gcf ( a, b )

{

r = a % b; # r is the Remainder of a / b (see rem)

if ( r == 0 ) return b;

else return gcf ( b, r );

}

1.a [20pts] Based on the given template (gcfr_example.s), rewrite the above function so that it uses an iterative loop instead of recursion. This will be enough to express the entire procedure as a Leaf procedure, which should therefore no longer use the stack. However, your answer must still contain all the other aspects of a procedure.

1.b [15pts] Estimate the number of instructions executed for each of the above implementations (gcfr & gcf), as a function of the number of times the remainder must be calculated before an answer is found. (This should be a linear function in both cases.)

1.c [15pts] How much of a difference does not recursing make? (Answers will certainly depend on how you count your instructions, and how elegant your code is.)

Instructions:

Add your implementation under corresponding assembly labels (gcf). Use the following sample dataset to finish your implementation.

list: .word 13, 13, 37, 600, 20, 100, 624129, 2061517

DO ALL PARTS A-D

the example code for part A is below:

.text

#.align 2

.globl main

main: la $t0, list

move $t1, $0 # init $t1 = 0

start: bge $t1, 4, exit # check loop condition

lw $a0, 0($t0) # load 1st arg

lw $a1, 4($t0) # load 2nd arg

jal gcfr # call gcfr or gcf

add $a0, $0, $v0 # move result to print argument

li $v0, 1 # print integer

syscall # system call for print result

addi $a0, $0, 0xA # ascii code for LF

addi $v0, $0, 0xB # syscall 11

syscall

addi $t1, $t1, 1 # increment $t1

add $t0, $t0, 8 # adjust index

j start # iterate

exit: li $v0, 10 # system call for exit

syscall # we are out of here

########## gcfr (non-leaf procedure) #######################

gcfr: # recursive version here

addi $sp, $sp, -4 # reserve space

sw $ra, 0($sp) # save return address to stack

move $v0, $a1 # v0 = b

remu $a1, $a0, $v0 # rem = a % b

bne $a1, $0, recur

addi $sp, $sp, 4 # restore stack

jr $ra

recur:

move $a0, $v0 # set next a = last $v0 = last b

jal gcfr

lw $ra, 0($sp) # restore return address

addi $sp, $sp, 4 # restore stack

jr $ra # return to caller

########## START of your modification: gcf #######################

#gcf: fill your implementation here

########## END of your modification #######################

.data

.align 0

list:

.word 13, 13, 37, 600, 20, 100, 624129, 2061517