Fibonacci

Motivation

It is important to always reduce the work, then parallelize if possible. In this studio you will build a beautiful, elegant solution to Fibonacci which can be easily parallelized yielding off-the-charts ideal parallelism. Sadly, it performs terribly since the work is exponential $\Phi ^{N}$. It is far better to build a linear time or log time algorithm even if it cannot be parallelized.

We will convert recurrence relations into code.

Additionally, (and of minor importance) We gain experience with the BigInteger class.

Background

The fibonacci sequence is a mathematical concept often used in computer science as a means to demonstrate iteration and recursion. Although you should be familiar with it from CSE 131, we will use the fibonacci sequence to demonstrate memoization and dynamic programming. Follow these links for a quick recap on memoization, dynamic programming, and the fibonacci sequence.

Where to Start

You will need to return the number associated with a given position in the fibonacci sequence. For example, if 0 was fed in, the method should return 0. 1 should return 1, 2 should return 1, 3 should return 2, and so on.

JUnit Test Suite

FibonacciTestSuite

Javadocs

Habanero

future(body)

interface HjFuture<V>.

get()

Common Mistakes To Avoid

use Habanero's HjFuture<V>, NOT java.util.concurrent's Future<V>

Check out Habanero#Future for pointers on using Habanero's futures.

use long, NOT int

lambdas will get cranky if you try to return an int instead of a long.

also, if you use ints in your calculation you will fail the tests when the result goes over Integer.MAX_VALUE.

Studio (Required)

RecurrenceRelationSequentialFibonacciCalculator

class:	RecurrenceRelationSequentialFibonacciCalculator.java
methods:	fibonacci
package:	fibonacci.studio
source folder:	student/src/main/java

implement a recursive method for:

recurrence relation

$F_{n}=F_{n-1}+F_{n-2}$

seed values

$F_{0}=0$

$F_{1}=1$

RecurrenceRelationParallelFibonacciCalculator

class:	RecurrenceRelationParallelFibonacciCalculator.java
methods:	fibonacci
package:	fibonacci.studio
source folder:	student/src/main/java

Use futures to add parallelism to the recurrence relation solution.

MemoizationSequentialFibonacciCalculator

class:	MemoizationSequentialFibonacciCalculator.java
methods:	fibonacciMemo
package:	fibonacci.studio
source folder:	student/src/main/java

Implement the recurrence relation algorithm but employ memoization for the win.

DynamicIterativeSequentialFibonacciCalculator

recurrence relation

if n is odd

$k={\dfrac {n+1}{2}}$

$F_{n}=(F_{k}\times F_{k})+(F_{k-1}\times F_{k-1})$

else

$k={\dfrac {n}{2}}$

$F_{n}=((2\times F_{k-1})+F_{k})\times F_{k}$

seed values

$F_{0}=0$

$F_{1}=1$

Fun (Optional)

MemoizationParallelFibonacciCalculator

Create all of your futures [0..N] up front and then call get on memo[n].

RoundPhiToTheNOverSqrt5SequentialFibonacciCalculator

${\dfrac {\Phi ^{n}}{\sqrt {5}}}$

Testing Your Solution

Correctness

class:	FibonacciTestSuite.java
package:	fibonacci.studio
source folder:	testing/src/test/java

Performance

class:	FibonacciIterations.java
package:	fibonacci.studio
source folder:	src/main/java