SI232 Spring 2006 Project #1: Fabulous Fibonacci Due Wed Feb 8

This project is to be completed independently, in accordance with the course policy.

This means collaboration between students is not permitted. 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 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. 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. 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.

3. 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.

4. 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: /Users/cs/lmcdowel/courses/si232/spim/

5. Use Alt-PrintScreen to generate a screenshot.

(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 SI232 directory. Name it Project1-section-lastname.asm

(e.g., Project1-1001-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?