CIT 594, Assignment 3: Fibonacci Numbers

About Fibonacci Numbers

The Fibonacci Sequence is a series of integers. The first two numbers in the sequence are both 1; after that, each number is the sum of the preceding two numbers.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

For example, 1+1=2, 1+2=3, 2+3=5, 3+5=8, etc.

The nth Fibonacci number is the nth number in this sequence, so for example fibonacci(1)=1, fibonacci(2)=1, fibonacci(3)=2, fibonacci(4)=3, etc. Do not use zero-based counting; fibonacci(4)is 3, not 5.

Your Assignment

Your assignment is to use Forté to write an applet that computes the nth Fibonacci number in three different ways, and to time each of the three methods. Details are given below.

Forté. I have written a short tutorial on using Forté (with and without pictures), which I strongly recommend that you step through before attempting to use it yourself. The tutorial is short, I promise; it shouldn't take you very long at all. (The tutorial that comes with Forté, it seems to me, is designed to show off all the things Forté can do, rather that get you started using it.) I think my tutorial covers everything you need to know about Forté for this assignment.

Simple recursive definition of Fibonacci. The nth Fibonacci number is usually defined as follows:

fibonacci(n) = if n <= 2, then 1
               else fibonacci(n-1) + fibonacci(n-2)

It is very simple to turn this into a recursive method--it's practically in Java already. This is the first version that you should get working.

Nonrecursive definition of Fibonacci. Next most difficult is to write a nonrecursive method to compute the nth Fibonacci number. As before, you are given n as an argument. This time, your method uses a loop and a small number of local variables. It's your job to figure out the details, but I'll say this much: for n>2, you need to start with the numbers 1 and 1, and work your way up to the desired number. You do not need an array, since you are ignoring any Fibonacci numbers older than the previous two.

Singly recursive definition of Fibonacci. Write a recursive version of the Fibonacci function that only contains one call to itself, rather than two. This is tricky; my suggestions will probably make more sense to you if you first try to figure out for yourself how to do it.

The problem is that computing the nth Fibonacci number requires knowing the two previous Fibonacci numbers, and a method only returns one result. We can't do anything about the former, but we can do something about the latter; we can define a method that returns two numbers. How? The trick is to define a new kind of object (that is, a new class) containing two numbers. For example, we might define a class Pair containing two long integers. If we design our function so that fibonacci(n) returns a Pair of numbers--the desired Fibonacci number along with the previous Fibonacci number--then we can write a recursive function that does essentially the same computations as the nonrecursive version. (Of course, when we use this function, we have to extract the one number we want to display from the Pair of numbers that it returns as a result.)

Applet description. The applet should contain:

Timing. Each time you compute a Fibonacci number, measure how many milliseconds it takes, and display this timing information. There is a Java function, System.currentTimeMillis(), which returns a long result; call it once before you do the computation, and a second time after you do the computation; subtract to get the elapsed time. Be careful to measure only the computation time; any changes to the GUI should be made either before or after you start measuring.

Also, since System.currentTimeMillis() uses clock time, not how long this particular process takes, you should avoid doing anything else while doing your timing tests. Don't download files or play music in the background, for example, or use any other programs in the foreground.

Your timing tests probably won't be absolutely consistent, because there are always background tasks that you can't do anything about--that's OK. Also, you may see the exact same computation occasionally take much longer than usual. This is because Java garbage collection may occur at any time. If you measure the exact same computation many times, and one result is much larger than the others, it's probably because of garbage collection. Ignore any results where you suspect garbage collection occurred.

When your program is running, try it out for some reasonable values of n. Make a small table (or three tables, if you prefer) of your results. Tell what you conclude is the time complexity of each version. This should not be a fancy writeup, just a few lines (like something you would e-mail to a friend). Put it on a file named readme.txt and turn it in along with your program.


What to turn in:

Put all your files--your .java files, your .class files, your .html file, your readme.txt file--into a single .jar file and turn it in via Blackboard by Midnight, Thursday January 31. (I will talk briefly about jar files in class, or put up a page on them, or both.)

As always, if you see any errors in this assignment, please let me know.