A4+: Fibonacci Sequence
150-400 points
0, 1, 1, 2, 3, 5, 8, 13, ... The Fibonacci Sequence may very well be one of the simplest yet intriguing sequences of numbers out there. Not only can it be found in nature in various forms but it also has some peculiar mathematical properties (for those interested, this page gives a nice overview).
For this assignment, you are asked to first implement two different approaches to a simple Fibonacci calculator (part 1) and then implement a simple Fibonacci REPL that uses persistent memory to avoid recalculation (part 2).
Part 1 (150 points)
The first part of the assignment is to get familiar with the calculation of the Fibonacci sequence. It consists of two different implementations for the same function.
This part is quite similar to assignments 3 & 4, it is recommended for everyone to at least give it a try after finishing the mandatory assignments!
Implement a subroutine with the following signature:
Use the a4plus-fib-iter.S file to give an iterative implementation and the a4plus-fib-rec.S file for a recursive implementation. Further, use the a4plus-fib-main.S file to give a simple main routine that gets a number from the user, calls the subroutine, and then pretty-prints the returned result. The output (for both versions) should look like this:
where <i> is the given input and <fib(i)> is the number in the Fibonacci sequence at index i.
Note for using the Framework
The iterative implementation of the assignment can be built and run with make a4plus-iter, while the recursive implementation can be built and run with make a4plus-rec.
If you are using the "Debug Current File" configuration of the debugger, it is necessary to have either the a4plus-fib-iter.S or a4plus-fib-rec.S file open in your active editor window.
Part 2 (250 points)
The second part of the assignment is all about saving and reusing results and some (slightly) more advanced user interaction. It requires you to work with explicit memory management (through functions like malloc, realloc, or free), which can be a bit of a challenge in a low-level language like Assembly.
Use the a4plus-fib-repl.S file for your implementations (main and my_fib) for this part.
Subroutine
Your implementations from Part 1 will recalculate the entire Fibonacci sequence for every call. This is quite wasteful for your compute resources (at least if you value computation time over storage in the so-called space-time-tradeoff). In this part of the assignment, you are addressing that issue with a reworked my_fib subroutine. The new signature is as follows:
This routine not only takes the index of the Fibonacci number to calculate (i) but now also takes a pointer to an array (arr) of already computed Fibonacci numbers (the length of which is indicated by size). It furthermore no longer returns a computed value, but rather also a pointer to an array. The arr argument can be NULL in the case that there are no pre-calculated numbers.
When the function is called, there are two possible executions:
: the Fibonacci sequence is already calculated up to the requested index
: the Fibonacci sequence is not yet calculated up to the requested index
Handling the first case is trivial (as no work has to be done and the array should stay untouched), for the second, however, the function should:
resize the array to fit the Fibonacci sequence up to the requested index
calculate the missing numbers (without recalculating any existing numbers)
return a pointer to the new array
while not allocating more memory than needed for the sequence or leaking any memory.
Main Program (REPL)
Write a main routine that continuously asks the user for an index and then prints the associated Fibonacci number, until the user enters a non-numeric input, at which point the program should exit gracefully (Hint: you may want to read the scanf man page to learn how inputs that do not match the format specifier are handled).
The output of a program run should look as follows:
The program should make use of the full functionality offered by the revised my_fib function, so properly keep track of the already calculated sequence of numbers (and its length). This will be tested by the TA handling your submission.
Last updated