CS 3410 Spring 2018
Due: Upload your implementation of the Iterative and/or Recursive Fibonacci by 11:59pm on Sunday, March 18th, 2018
Optional: If you upload your memoized version, we will run it through the auto-grader, too.
(Only the highest of the iterative, recursive, or memoized scores counts for this lab grade, but all three versions will be turned in again and graded again as part of your next project, so it is in your best interests to get feedback early on.)
In this lab you will re-visit the fibonacci programs that you worked on in a previous project.
The Fibonacci sequence is defined as follows: start
with 0, 1; for the code you are implementing, the zeroth Fibonacci number is
defined to be 0, and the first Fibonacci number is defined to be 1. To
obtain subsequent numbers in the sequence, we take the sum of the previous
two numbers in the sequence. Thus, the second number in the seqeuence is
0 + 1 = 1, and the third number in the sequence is 1 + 1
= 2. The function you implement will return the nth Fibonacci number,
where the value n is an input to your function.
There are several ways to compute the Fibonacci sequence. You will implement one (optionally, more) of the methods below (please do not submit MIPS code with any form of main function).
Iterative Fibonacci: An efficient approach for computing the answer for just a single index in the sequence.
int i_fibonacci(int n) {
int f1 = 0;
int f2 = 1;
int fi;
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
for (int i = 2; i <= n; i++) {
fi = f1 + f2;
f1 = f2;
f2 = fi;
}
return fi;
}Recursive Fibonacci: Simple but inefficient. Logisim will be too slow to use this version except when the index is small.
int r_fibonacci(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
return r_fibonacci(n-2) + r_fibonacci(n-1);
}Memoization Fibonacci: For computing the answer for more than one index, it makes sense to remember previously computed answers since answers for larger indices require answers for smaller indices. So if fibonacci(40) and fibonacci(39) has already been computed, then it is easy to compute fibonacci(41). This memoization version is essentially the same as the recursive version but takes two extra arguments: an array log_array of previously computed answers (should be initialized to all zeros), and the number of entries size in the array.
Note: the memoized Fibonacci does not allocate or initialize the
array. It assumes that the function calling m_fibonacci has already
created an array of size size and initialized every entry to zero.
int m_fibonacci(int n, int log_array[], int size) {
if (n < size && log_array[n] != 0) { // non-zero means we already computed this
return log_array[n];
}
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
int answer = m_fibonacci(n-2, log_array, size) + m_fibonacci(n-1, log_array, size);
if (n < size) {
log_array[n] = answer; // save answer for reuse later
}
return answer;
}Implement one (optionally, more) of these versions of the Fibonacci function using MIPS assembly code. They must all work on your processor in Logisim, though you will have be careful when testing to select indices whose Fibonacci number can be computed in a reasonable time.
Your Fibonacci functions should follow the calling convention covered in
lecture. In particular, they should get their inputs from the argument
registers ($a0, $a1, etc.) and return their outputs in
the result register $v0. If you want to test each function, you can
create a "main" program which initializes the stack (by setting $sp
and $fp to something reasonable and usable) and calls the function
on an input. If you add testing code to a file, make sure to turn in
a version without the testing code. Since all of your functions will
follow the calling convention, you'll invoke them from your main program by
loading the input registers, saving caller-saved registers if necessary, and
then executing a JAL instruction.