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. It is far better to build a linear or log time algorithm whether or not it can be parallelized.

We will gain experience with the future construct.

We will convert recurrence relations into code.

Additionally, (and of minor importance) we gain experience working 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.

Scientific American Video:

The Core Questions

• What are the tasks?
• What is the data?
• Is the data mutable?
• If so, how is it shared?

Code To Use

Parallel Docs

V5

future(body)

interface Future<V>.

get()

Check out the wiki's reference page to see how Future's can be used!

BigInteger Docs

fibonacci(47) is greater than Integer.MAX_VALUE which would overflow if we used the primitive int data type. We use BigInteger instead to prevent this problem.

BigInteger

BigInteger.ZERO

BigInteger.ONE

bi.add(other)

bi.multiply(other)

bi.valueOf(val)

bi.shiftLeft(n)

Studio (Required)

RecurrenceRelationSequentialFibonacciCalculator

Work:

$O(\Phi ^{n})$

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

method: public BigInteger fibonacci(int n) (sequential implementation only)

implement a recursive method for:

recurrence relation

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

seed values

$F_{0}=0$

$F_{1}=1$

RecurrenceRelationParallelFibonacciCalculator

Work:	$O(\Phi ^{n})$
CPL:	$O(n)$
Ideal Parallelism:	${\dfrac {\Phi ^{n}}{n}}$

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

method: public BigInteger fibonacci(int n) (parallel implementation required)

Use futures to add parallelism to the recurrence relation solution.

MemoizationSequentialFibonacciCalculator

Work:

$O(n)$

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

method: private BigInteger fibonacciMemo(BigInteger[] memos, int n) (sequential implementation only)

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

	@Override
	public BigInteger fibonacci(int n) {
		BigInteger[] memos = new BigInteger[n + 1];
		return fibonacciMemo(memos, n);
	}

Warning: Do NOT invoke fibonacci from fibonacciMemo. Invoke fibonacciMemo from fibonacciMemo.

Warning: The entire point of memoization is to avoid recalculating the same computation. Be sure to store the value for each calculation as it is made even if that means splitting up a line of code.

DynamicIterativeSequentialFibonacciCalculator

Work:

$O(n)$

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

method: public BigInteger fibonacci(int n) (sequential implementation only)

Imagine you are simply writing out Fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13...

Convert that process of summing the two previous numbers over and over into code.

LinearRecurrenceSequentialFibonacciCalculator

Work:

$O(n)$

note: can be memoized to

Work:

$O(\log {}n)$

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

method: public BigInteger fibonacci(int n) (sequential implementation only)

Warning: Do NOT invoke fibonacci(k) or fibonacci(k-1) multiple times if you can catch the result in a variable and reuse it.

Tip: There is no need to store k in a BigInteger. Since it is smaller than n, it will fit just fine in an int.

Tip: You can shift left by 1 if you would prefer to not have to multiply by the big integer value of 2.

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)

RecurrenceRelationParallelWithThresholdFibonacciCalculator

Similar to #RecurrenceRelationParallelFibonacciCalculator but with a threshold in place to prevent creating too many tasks for the number of processors.

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:	FibonacciTiming.java
package:	fibonacci.studio
source folder:	src/main/java

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