#### Lab 1060 - Three Little Fibs

##### Description

In this lab, you will compute Fibonacci numbers using three different classes, each of which implements the same FindFib interface.

Recall the Fibonacci sequence:

```1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
```

The first two numbers are both one. Starting with the third number, any Fibonacci number is the sum of the two previous numbers. For simplicity, we refer to the first Fibonacci number as F(1). Looking at the sequence, you should see that F(10) is 55.

##### Assignment

Calculate F(40) using three techniques: a simple iteration, a single formula that uses the golden ratio, and recursion. Each of these is encapsulated in a separate class, named FibIteration, FibFormula and FibRecursion respectively. Each implements the FindFib interface.

For the formula version, use Binet's Formula:

```F(n) = (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n) / sqrt(5)
```

You will create five Java source files: TestFib.java (the test program), FindFib.java (the interface definition) and the three classes that implement the FindFib interface.