|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, ...
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 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
two long integers. If we design our function so that
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
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
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.
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
Fibonacci, and don't pass any parameters from the HTML file into the applet. (This is for our convenience in testing.)
longvalues rather than
intvalues. Fibonacci numbers can get large in a hurry. You also need
longvalues to do the time computations.
What to turn in:
Put all your files--your
.java 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,
As always, if you see any errors in this assignment, please let me know.