Java (please show your math !)

Memoization

The time complexity is exponential so this simplistic recursive approach becomes intractable when we get into the fifties or so. We can greatly increase our time performance with memoization that is, every time we compute a value we make a note (or memo) of it and check that memo list before computing.

Add memoization to your Fibonacci program. At what point does the computation time become more than one second?

Fixed-Width Integers

Now our program is fast; the next problem is that in the mid-nineties the size of the Fibonacci number exceeds the capacity of the long data type.

What is the largest Fibonacci Number that you can successfully compute using long?

n = _________

To compute larger Fibonacci numbers we must make use of arbitrary-length integers: the BigInteger class. Modify your program to use BigInteger and compute the following Fibonacci numbers:

n = 50 value =

n = 90 value =

n = 100 value =

n = 150 value =

n = 200 value =

n = 250 value =

n = 300 value =

Note: you can verify your results by looking up the values online.

At what point does your code require more than one second to run? Test with powers of ten; compute Fibonacci Numbers 100, 1000, 10000, 100000, and so on until you exceed one second. Then home in on the particular value that requires right at one second (1000 ms) to compute.