**IC220 Spring 2008 Project #1: Fabulous Fibonacci Due Wed Feb 6**

**This project must
be completed independently (unlike regular assignments).**

**This means
collaboration between students is not permitted. Online sources (aside
from IC220’s website) are also prohibited.
You may consult your notes, textbook, and the instructor. See the
instructor for help or clarification.**

Background: You have already had experience with writing simple
MIPS programs and testing them with SPIM.
In this project you will review and integrate your understanding of:

1.
General MIPS programming

2.
Function calls

3.
Recursion

**Task: **Write a **recursive** MIPS
program that computes a term in the Fibonacci sequence. This sequence of numbers

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …) can be computed with the following
recursive function:

int
fibonacci (int N) {

if (N < 2)

return N;

else

return fibonacci(N-1) + fibonacci(N-2);

}

Thus, Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) =
2, …. Fib(10) = 55. Be sure you aren’t
off by 1 in the sequence.

There are much more efficient ways to compute the
Fibonacci series, but to solidify your understanding of recursion and the stack
you are __required to have a recursive solution__.

**Specifics**: Starter code is provided: FibonacciStarter.asm. **Start with this!!!**! You should do the
following with this code:

1. Modify the main function to:

Print a welcome message that
includes your name

Call the fibonacci procedure to compute the Fibonacci
term requested by the user

Print the calculated term after it
has been returned to the main function

2. Write a procedure called fibonacci that:

Recursively
calculates the Nth Fibonacci term, where N comes from the argument passed in
register $a0.

Returns
the value in $v0.

You do not have to write
this function from scratch – translate the C code given above!

3. Test your code with SPIM.

Sample screen shot of completed program:

Tips:

1.
Start early! Recursion can be tricky. Allow time to get help from the instructor if
needed.

2.
But don’t make this harder than it needs to be! Your primary task is to simply translate the C code above to a
MIPS function. While this function is
recursive, really this is just another example of a nested procedure – follow
the rules for nested procedures and recursion will take care of itself.

3.
You
will need to use the stack. Be sure you
begin, make sure you understand how to do this and what will need to be saved
and restored with the stack.

4.
This
assignment requires you to write only about 30 carefully chosen assembly
instructions. If you have many more than that, you probably
are misunderstanding what should be done.

5.
The
following material may be helpful to you:

·
Lecture
notes on MIPS procedure calls, and SPIM

·
Lab
#1, where you first used SPIM

·
SPIM
reference material: http://www.usna.edu/Users/cs/lmcdowel/courses/ic220/spim/

6.
Use
Alt-PrintScreen to generate a screenshot.

7.
An
error message like “Can’t add 8 bytes to Lstack” means you are stuck in
infinite recursion.

8.
Use
the starter code!

(more on back)

Deliverables:
(1 through 3 handed in, stapled together in the following order)

1) A cover sheet with your
feedback. (10
pts)

2) Screenshot showing your program
computing Fib(10) (10
pts)

3) Printout of your __recursive __assembly
code (60
pts)

4) .asm file saved to your X drive (20
pts)

Place this file in your IC220
directory. Name it
Project1-section-lastname.asm

(e.g., Project1-2001-smith.asm).

Extra credit (up to 5 pts each):

1. Write a new program to calculate the Fibonacci
numbers in a non-recursive manner. Turn
in this program and a screenshot showing the calculation of Fib(30).

2. Write a new program to calculate the Fibonacci
numbers using the floating point registers to keep track of the calculations
(you can assume that you only have to deal with numbers with no fractional
part). Why might you want to do this?