Question A)

The MIPS ISA

Computing a Fibonacci Number

The Fibonacci number Fn is recursively defined as F (n) = F (n 1) + F (n 2),

where F (1) = 1 and F (2) = 1. So, F (3) = F (2) + F (1) = 1 + 1 = 2, and so on.

Write the MIPS assembly for the fib(n) function, which computes the Fibonacci number F (n):

int fib(int n) {

int a = 0; int b = 1; int c = a + b;

while (n > 1) {

c = a + b;

a = b;

b = c;

n--;

}

return c;

}

Remember to follow MIPS calling convention and its register usage (just for your reference, you may not need to use all of these registers):

The argument n is passed in register $4.

The result (i.e., c) should be returned in $2.

$8 to $15 are caller-saved temporary registers.

$16 to $23 are callee-saved temporary registers.

$29 is the stack pointer register.

$31 stores the return address.