JAVA LAB

Loop and Recursive Fibonacci Function:

Write two functions to compute Fibonacci numbers: one using a loop, and the other recursive as described in class. The two methods are

public long fibonacci_loop(int f){}

public long fibonacci_recursive(int f){}

We expect the recursive version to be slower for large integers, much slower than the loop version. Measure the time required to perform these computations with the following code:

long t1 = System.currentTimeMillis();

// do something that requires a lot of time

long t2 = System.currentTimeMillis();

System.out.println("The elapsed time is " + ( t2 - t1 ) / 1000. + " seconds.");

How much time is required to compute the following Fibonacci numbers using a loop?

n = 10 time required: ___________

n = 50 time required: ___________

n = 90 time required: ___________

How much time is required to compute the following Fibonacci numbers using recursion?

n = 30 time required: ___________

n = 40 time required: ___________

n = 41 time required: ___________

n = 42 time required: ___________

n = 43 time required: ___________

n = 44 time required: ___________

n = 45 time required: ___________

n = 46 time required: ___________

n = 47 time required: ___________

n = 48 time required: ___________

n = 49 time required: ___________

n = 50 time required: ___________

Determine the largest values of n for which the corresponding Fibonacci Numbers can be computed within the given time.

n = _____ time required: less than 10 seconds

n = _____ time required: less than 30 seconds

n = _____ time required: less than 1 minute

n = _____ time required: less than 5 minutes

Estimate the value of n for the largest value of fib(n) that can be computed using recursion in one hour on your computer. Explain in detail how you estimated this value. Also describe any additional data you took to arrive at this value. Attach any additional work required.

n = ______ for time required = 1 hour (3600 seconds)

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one day (86,400 seconds).

n = ______ for time required = 1 day (86,400 seconds)

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one year.

n = ______ for time required = 1 year.

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one million years (10⁶ years).

n = ______ for time required = 1 million years.

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.

Loop and Recursive Factorial Function:

Use the same timer techniques as described on the previous page.

The two methods are

public int factorial_loop(int n){}

public int factorial_recursive(int n){}

Determine the largest input value n for which a factorial can be computed using int.

What was the largest result for factorial using int? n = ______________

n! = ______________

What was the elapsed time computing this factorial using loops? t = _______________

Change the data type to long and repeat the above tests. n = ______________

n! = _____________

What was the elapsed time computing this factorial using loops? t = _______________

What is the elapsed time computing this factorial using recursion? t = _______________

Are these times significantly different? Why or why not? Answer in the space below:

Change the data type to BigInteger. Can you find a value for which it requires 1 second to compute the factorial?

v =