**
Week 9: Lab Document, 10/25
**

As discussed in class, the classic, recursive implementation of the computation of
the `n` fibonacci number is horribly slow.
Here is an example of this implementation: Fibonacci.java.
Here is some output I got from running this program; the 10th, 20th, and 30th Fibonacci numbers
are easily computed, but the 40th Fibonacci number takes 770 milliseconds, and the
50th took 94276 milliseconds (more than a minute).
I was unable to get fibonacci(60) to terminate with 15-20 minutes!

The 10th Fibonacci number is 55
It took 0 milliseconds to compute it.
The 20th Fibonacci number is 6765
It took 2 milliseconds to compute it.
The 30th Fibonacci number is 832040
It took 10 milliseconds to compute it.
The 40th Fibonacci number is 102334155
It took 770 milliseconds to compute it.
The 50th Fibonacci number is -298632863
It took 94276 milliseconds to compute it.

The things to note are (i) the explosion in running time and (ii) the fact that the 50th
Fibonacci number is reported as being negative.
Of course, (ii) is due to "integer overflow" and is easily fixed by using the
BigInteger class
defined in `java.math`.
It is more interesting to try and deal with the explosion in running time.
An easy (but, somewhat uninteresting) fix is to get rid of recursion entirely and
just use a simple iterative algorithm that uses 2-3 variables to keep track
of the last two elements of the fibonacci sequence.
A more interesting approach is to keep the recursion more or less intact, but speed
it up greatly by observing that

- the slowness of the standard, recursive implementation of fibonacci numbers
is due to the same computation being repeated many many times, and
- these multiple, identical computations can be avoided by remembering
old answers in a table.

**Problem.**
Implement a "fast" version of a recursive fibonacci number computation.
To compute the `n`th Fibonacci number define an array of `answers` of
size `n`.
The idea is that the value of the `k`th Fibonacci number will be stored
in slot `k`-1, as soon as it is computed the very first time.
Subsequently, whenever fibonacci(`k`) is needed a constant time table lookup
will suffice.
The `answers` table is initialized to 0; in general, 0 in a slot indicates
that the corresponding answer has not yet been computed.
Using the fast, recursive fibonacci function, compute the 500th Fibonacci number.