Mips Labs Using SPIM - Lab 4

The Fibonacci Sequence
Function Calls in MIPS
Writing Your Program
Turning In Your Code
Conclusion

The Fibonacci Sequence

The first two elements of the Fibonacci sequence are 0 then 1. The value of every following element is the sum of the preceding two elements. For example, let Fib(n) represent the n^th element of the Fibonacci sequence so Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, etc.

Here is a table with a few more values:

n:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	...
Fib(n):	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	...

High level code for calculating a Fibonacci value

Here is some sample C++ code for a recursive procedure which calculates a specified element of the Fibonacci sequence:

int getFibonacci(int num)
{
  if (num == 0) {
    return 0;
  } else if (num == 1) {
    return 1;
  } else {
    return getFibonacci(num - 1) + getFibonacci(num - 2);
  }
}

Note: don't worry about error handling. You can assume that only integers greater than or equal to zero are passed into the function.

Back to Top

Function Calls in MIPS

Appendix A of the text book contains information about procedure calls in MIPS including conventions for proper use of registers and the stack. You must correctly follow these conventions. Additionally, there is an example of an implementation of the factorial function, which is also recursive. You should use this as an example and a general template.
(The factorial example can also be downloaded from here: factorial.spim)

Back to Top

Writing Your Program

Write a program in MIPS that contains a procedure which takes one argument - an integer greater than or equal to zero which specifies which element of the Fibonacci sequence is to be returned. The procedure must be recursive and return the correct Fibonacci value. Also, include a "main" section with at least one call to that function.

Back to Top

Turning In Your Code

Turn in your code by emailing it to the TA, Yuly, at ysuvorov@cs.iastate.edu. The subject line of your email should be "ComS 321 Lab 4" and you should paste the assembly code into the message body.

Back to Top

Conclusion

In this lab, you have learned about procedure calls in MIPS by writing a program containing a recursive procedure to calculate elements of the Fibonacci sequence. This should give you basic familiarity with procedure calling conventions including register and stack handling.

Back to Top