Difference between revisions of "Fibonacci"

From CSE231 Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
=Motivation=
 
=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 <math>\Phi^N</math>.  It is far better to build a linear time or log time algorithm independent of if can or cannot be parallelized.
+
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 gain experience with the future construct.

Revision as of 20:44, 5 February 2018

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.

Javadocs

V5

future(body)

interface Future<V>.

get()

BigInteger

BigInteger.ZERO
BigInteger.ONE
bi.add(other)
bi.multiply(other)

Common Mistakes To Avoid

Attention niels epting.svg 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.

Studio (Required)

RecurrenceRelationSequentialFibonacciCalculator

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

implement a recursive method for:

recurrence relation

seed values

Work:

RecurrenceRelationParallelFibonacciCalculator

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

Use futures to add parallelism to the recurrence relation solution.

Work:
CPL:
Ideal Parallelism:

MemoizationSequentialFibonacciCalculator

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

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);
	}
Work:

DynamicIterativeSequentialFibonacciCalculator

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

LinearRecurrenceSequentialFibonacciCalculator

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

recurrence relation

if n is odd
else

seed values

Work:

Fun (Optional)

DynamicRecursiveSequentialFibonacciCalculator

MemoizationParallelFibonacciCalculator

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

RoundPhiToTheNOverSqrt5SequentialFibonacciCalculator

Testing Your Solution

Correctness

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

Performance

class: FibonacciIterations.java Noun Project stopwatch icon 386232 cc.svg
package: fibonacci.studio
source folder: src/main/java