> For the complete documentation index, see [llms.txt](https://computerscienceeducation.gitbook.io/co-lab-manual/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://computerscienceeducation.gitbook.io/co-lab-manual/assignments/extra-assignments/a3-b-fibonacci-repl.md).

# A3-b: Fibonacci REPL

{% hint style="info" %}
**CMake target**: `a3b` 

```bash
cmake --build .build --target a3b
```

{% endhint %}

{% hint style="danger" %}
You can receive points for either A3-a or A3-b, but not both!
{% endhint %}

Computing a number from the Fibonacci Sequence can be very time consuming and repetitive especially if you previously computed that number. Why not spice your implementation of the Fibonacci Sequence up a bit by considering a REPL version?

This 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 `a3b-fib-repl.S` file for your implementations (`main` and `my_fib`) for this part.

***

### Subroutine

The implementations from A3-a 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 assignment, you are addressing that issue with a reworked `my_fib` subroutine. The new signature is as follows:

```c
uint64_t *my_fib(uint64_t i, uint64_t *arr, uint64_t size)
```

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:

1. $$\texttt{size} > \texttt{i}$$: the Fibonacci sequence is already calculated up to the requested index
2. $$\texttt{size} \le \texttt{i}$$: 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](https://en.wikipedia.org/wiki/Memory_leak).

***

### 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:

```
Enter an index: <x>
F_<x> = <fib(x)>
Enter an index: <y>
F_<y> = <fib(y)>
Enter an index: <z>
F_<z> = <fib(z)>
Enter an index: q
Exiting...
```

{% hint style="warning" %}
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**.
{% endhint %}

***

### Memory safety

Starting from this assignment, you will work closely with memory allocation and manipulation. We expect your program to precisely handle memory, without any memory errors. The CodeGrade environment will test whether your program safely accesses and releases memory, by means of address sanitization.

It is now the perfect time to familiarize yourself with [address sanitization and memory errors](/co-lab-manual/reference-documentation/address-sanitization.md). All upcoming assignments will require *an intuition* for memory-related issues, which would ideally be developed during this assignment.&#x20;