CS 3410 Fall 2018
Due: Check off your implementation of the Recursive Fibonacci in Lab or by 11:59pm on Sunday, October 7th, 2018
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 the recursive method below. Please do not submit MIPS code with any form of main function (e.g. instruction that set n to a specific value), we will run it with our own values.
Recursive Fibonacci: Simple but inefficient. Logisim would 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);
}Implement this version of the Fibonacci function using MIPS assembly code. It must work on the online simulator, though you will have to be careful when testing to select indices whose Fibonacci number can be computed in a reasonable time.
Your Fibonacci function should follow the calling convention covered in
lecture. In particular, it should get its inputs from the argument
registers ($a0, $a1, etc.) and return its outputs in
the result register $v0. If you want to test the 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 your function 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.
As a reminder, don't forget to save the previous value in callee-saved registers before you use them in your function!
You can use the following template as your main function, however, you must change the values for the function to work:
addiu $sp, $0, 0
addiu $fp, $0, 0
addiu $a0, $0, 0
jal r_fibonacci
nop
j exit
nop
r_fibonacci:
// Your function here
exit:
Recursive fibonacci only uses one argument and doesn't access memory. Binary search takes four arguments and accesses array elements stored in memory. For a bit more challenge, implement the following in MIPS assembly code.
// Find index of x in arr within the bounds l and r
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l)/2; // How do you divide by two??
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
// Convert the following main function to run your code
int main(void) {
int arr[] = {2, 3, 4, 10, 40}; //Store these values in memory somewhere
int n = 5;
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
return result;
}