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:

- Your name
- Three
*labeled*text fields:- an editable text field for typing in
`n`

- a noneditable text field for displaying the result, and
- a noneditable text field for displaying how long the computation took

- an editable text field for typing in
- Three buttons, with the following (suggested) labels:
**2 Recursions**, for calling the doubly-recursive version of Fibonacci**1 Recursion**, for calling the singly recursive version, and**No Recursions**, for calling the nonrecursive version

- Some indication as to whether the program is waiting for input, or is busy computing a Fibonacci number.

**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.

**Notes.**

- Please name your applet
`Fibonacci`

, and don't pass any parameters from the HTML file into the applet. (This is for our convenience in testing.) - Most important, use
`long`

values rather than`int`

values. Fibonacci numbers can get large in a hurry. You also need`long`

values to do the time computations. - I shouldn't need to say this, but--all three versions of your Fibonacci
method should return the
*same answer*for any given value of`n`

. - It will be easiest to give your three Fibonacci methods three different names. That's an implementation detail that the user (me) should not have to know about.

**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.