Difference between revisions of "Fibonacci"

From CSE231 Wiki
Jump to navigation Jump to search
 
(71 intermediate revisions by 2 users not shown)
Line 11: Line 11:
 
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 [http://classes.engineering.wustl.edu/cse231/core/index.php/FAQ#Unit_2:_Futures.2FAccumulators.2FData_Races.2FMemoization memoization, dynamic programming], and the [https://en.wikipedia.org/wiki/Fibonacci_number fibonacci sequence].
 
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 [http://classes.engineering.wustl.edu/cse231/core/index.php/FAQ#Unit_2:_Futures.2FAccumulators.2FData_Races.2FMemoization memoization, dynamic programming], and the [https://en.wikipedia.org/wiki/Fibonacci_number fibonacci sequence].
  
==Javadocs==
+
==Ted Talk==
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html V5]
+
<youtube>SjSHVDfXHQ4</youtube>
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html#future-edu.wustl.cse231s.v5.api.CheckedCallable- future(body)]  
+
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html interface Future<V>].   
+
==Scientific American==
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get()]
+
[https://www.scientificamerican.com/video/the-mind-blowing-mathematics-of-sunflowers/ Mathematics of Sunflowers]
 +
 
 +
[[File:Fibonacci spiral.jpg|400px|link=https://www.scientificamerican.com/video/the-mind-blowing-mathematics-of-sunflowers/]]
 +
 
 +
<!--
 +
=Lecture=
 +
[https://docs.google.com/presentation/d/1Q4gzoclVBFmkKvX3W80rpGBBBPkXDe3q6IPW0iTKpSw/pub slides]
 +
 
 +
<youtube>l1hZiAXAcqI</youtube>
 +
 
 +
<youtube>mRZpq4KPMkY</youtube>
 +
-->
 +
 
 +
=Code To Use=
 +
==BigInteger Docs==
 +
fibonacci(47) is greater than [https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#MAX_VALUE Integer.MAX_VALUE] which would [https://en.wikipedia.org/wiki/Integer_overflow overflow] if we used the [https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html primitive int data type].  We use [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html BigInteger] instead to prevent this problem.
 +
 
 
[https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html BigInteger]
 
[https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html BigInteger]
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#ZERO BigInteger.ZERO]
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#ZERO BigInteger.ZERO]
Line 21: Line 37:
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#add-java.math.BigInteger- bi.add(other)]
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#add-java.math.BigInteger- bi.add(other)]
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#multiply-java.math.BigInteger- bi.multiply(other)]
 
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#multiply-java.math.BigInteger- bi.multiply(other)]
 +
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#valueOf-long- bi.valueOf(val)]
 +
: [https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#shiftLeft-int- bi.shiftLeft(n)]
 +
 +
=Studio (Required)=
  
=Common Mistakes To Avoid=
+
For the required part of the studio, you will be implementing a Fibonacci calculator five different ways. Some will be in parallel, some won't. The goal for each is to simply have it return the nth Fibonacci number that is initially passed through
{{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==
 
==RecurrenceRelationSequentialFibonacciCalculator==
 
{{Work|<math>O(\Phi^n)</math>}}
 
{{Work|<math>O(\Phi^n)</math>}}
 
{{CodeToImplement|RecurrenceRelationSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
 
{{CodeToImplement|RecurrenceRelationSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
implement a recursive method for:
+
 
 +
{{Sequential|public BigInteger fibonacci(int n)}}
 +
 
 +
The first file to complete is the basic recursive solution to Fibonacci. This should be done sequentially, and won't look too different from when you did it back in 131. Remember that instead of adding integers, we are using BigIntegers, so make sure to properly handle those.
  
 
===recurrence relation===
 
===recurrence relation===
Line 42: Line 63:
 
{{WorkCPLIdealParallelism|<math>O(\Phi^n)</math>|<math>O(n)</math>|<math>\dfrac{\Phi^n}{n}</math>}}
 
{{WorkCPLIdealParallelism|<math>O(\Phi^n)</math>|<math>O(n)</math>|<math>\dfrac{\Phi^n}{n}</math>}}
 
{{CodeToImplement|RecurrenceRelationParallelFibonacciCalculator|fibonacci|fibonacci.studio}}
 
{{CodeToImplement|RecurrenceRelationParallelFibonacciCalculator|fibonacci|fibonacci.studio}}
Use futures to add parallelism to the recurrence relation solution.
+
{{Parallel|public BigInteger fibonacci(int n)}}
 +
 
 +
Now make the solution you just wrote parallel, such that <code>fibonacci(n-1)</code> and <code>fibonacci(n-2)</code> are being solved at the same time. Do this by using futures. Make sure to call future.get() at the right time so there is sufficient parallelism.
 +
 
 +
{{Warning|The parallelism tests assume that you limit your base cases to 0 and 1, so please do NOT add a base case for 2.}}
 +
 
 +
== join vs future.get() ==
 +
 
 +
{{Warning|RecurrenceRelationParallelFibonacciCalculator.java does not contain the static import for join.}}
 +
 
 +
You can either include the static import:
 +
 
 +
<code>import static fj.FJ.join;</code>
 +
 
 +
and use <code>join</code> or
  
 +
invoke <code>future.get()</code>:
 +
 +
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html interface Future<V>]. 
 +
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get()]
  
 
==MemoizationSequentialFibonacciCalculator==
 
==MemoizationSequentialFibonacciCalculator==
 
{{Work|<math>O(n)</math>}}
 
{{Work|<math>O(n)</math>}}
 
{{CodeToImplement|MemoizationSequentialFibonacciCalculator|fibonacciMemo|fibonacci.studio}}
 
{{CodeToImplement|MemoizationSequentialFibonacciCalculator|fibonacciMemo|fibonacci.studio}}
Implement the recurrence relation algorithm but employ memoization for the win.
+
{{Sequential|private BigInteger fibonacciMemo(BigInteger[] memos, int n)}}
  
 +
The recurrence relation algorithm for Fibonacci has a lot of repeated calculations. For example, if we want fibonacci(10), we need to calculate fibonacci(9) and fibonacci(8), but during the calculations of fibonacci(9), we also calculate fibonacci(8), so that part is getting repeated. The bigger the number, the more repetition there is and the larger impact it has on our performance. The smart way to get around this is memoization. By storing our calculation results (in this case, with an array), we can simply refer to the work we've already done rather than doing it again.
 +
 +
Implement the recurrence relation algorithm again (sequentially), but employ memoization this time for the win. Make sure to store your work, and only do more work if it hasn't yet been done.
 +
 +
'''provided fibonacci method: '''
 
  <nowiki> @Override
 
  <nowiki> @Override
 
public BigInteger fibonacci(int n) {
 
public BigInteger fibonacci(int n) {
Line 55: Line 99:
 
return fibonacciMemo(memos, n);
 
return fibonacciMemo(memos, n);
 
}</nowiki>
 
}</nowiki>
 +
 +
{{Tip | you need not edit the <code>fibonacci</code> method.  You should only need to edit the <code>fibonacciMemo</code> method.}}
 +
 +
{{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==
 
==DynamicIterativeSequentialFibonacciCalculator==
 
{{Work|<math>O(n)</math>}}
 
{{Work|<math>O(n)</math>}}
 
{{CodeToImplement|DynamicIterativeSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
 
{{CodeToImplement|DynamicIterativeSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
 +
{{Sequential|public BigInteger fibonacci(int n)}}
 +
 +
In the previous algortihms, we've been tackling this problem from the top-down. But that isn't always the easiest way to think about the problem. Imagine you are simply writing out Fibonacci numbers:
 +
 +
: 0, 1, 1, 2, 3, 5, 8, 13...
 +
 +
You (assuming you aren't a human super-computer) start from the very bottom, and keep working the sequence up to your answer.
 +
 +
Recall from the lecture where we described calculating each subsequent value based solely on the previous two.
 +
 +
[[File:Dynamic fibonacci slide.png|400px]] [https://docs.google.com/presentation/d/1Q4gzoclVBFmkKvX3W80rpGBBBPkXDe3q6IPW0iTKpSw/pub?slide=id.g71e76e37ea_0_271 slide]
 +
 +
How would you go about converting this process into code?  Note: it should be sequential, and ''not have any recursive calls''.
 +
 +
=Challenge (Optional)=
 
==LinearRecurrenceSequentialFibonacciCalculator==
 
==LinearRecurrenceSequentialFibonacciCalculator==
{{Work|<math>O(\log{}n)</math>}}
+
{{Work|<math>O(n)</math>}}
 +
 
 +
note: can be memoized to {{Work|<math>O(\log{}n)</math>}}
 
{{CodeToImplement|LinearRecurrenceSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
 
{{CodeToImplement|LinearRecurrenceSequentialFibonacciCalculator|fibonacci|fibonacci.studio}}
 +
{{Sequential|public BigInteger fibonacci(int n)}}
 +
 +
Thanks to how awesome math is, we can actually solve the ''n''th Fibonacci number without knowing those for n-1 and n-2. We have provided the algorithm below. It is your job to translate this into code. Keep it sequential.
 +
 +
Once you finish with this, make sure to go back and compare the performance speed of all five of these algorithms. The results are very thought-provoking!
 +
 
===recurrence relation===
 
===recurrence relation===
  
Line 75: Line 147:
  
 
:: <math>F_n = ((2 \times F_{k-1}) + F_{k}) \times F_{k}</math>
 
:: <math>F_n = ((2 \times F_{k-1}) + F_{k}) \times F_{k}</math>
 +
  
 
===seed values===
 
===seed values===
Line 81: Line 154:
 
: <math>F_1=1</math>
 
: <math>F_1=1</math>
  
=Fun (Optional)=
+
{{Warning | Do NOT invoke <code>fibonacci(k)</code> or  <code>fibonacci(k-1)</code> multiple times if you can catch the result in a variable and reuse it. }}
==DynamicRecursiveSequentialFibonacciCalculator==
+
{{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.}}
 +
 
 +
=More Fun (Optional)=
 +
==RecurrenceRelationParallelWithThresholdFibonacciCalculator==
 +
Similar to [[#RecurrenceRelationParallelFibonacciCalculator]] but with a predicate in place to prevent creating too many tasks for the number of processors.
 +
 
 
==MemoizationParallelFibonacciCalculator==
 
==MemoizationParallelFibonacciCalculator==
 
Create all of your futures [0..N] up front and then call get on memo[n].
 
Create all of your futures [0..N] up front and then call get on memo[n].
 
+
==DynamicRecursiveSequentialFibonacciCalculator==
 
==RoundPhiToTheNOverSqrt5SequentialFibonacciCalculator==
 
==RoundPhiToTheNOverSqrt5SequentialFibonacciCalculator==
 
<math>\dfrac{\Phi^n}{\sqrt{5}}</math>
 
<math>\dfrac{\Phi^n}{\sqrt{5}}</math>
Line 91: Line 170:
 
=Testing Your Solution=
 
=Testing Your Solution=
 
==Correctness==
 
==Correctness==
{{TestSuite|FibonacciTestSuite|fibonacci.studio}}
+
===Studio (Required)===
 +
{{TestSuite|_FibonacciTestSuite|fibonacci.exercise}}
 +
===Challenge (Optional)===
 +
{{TestSuite|ChallengeFibonacciTestSuite|fibonacci.challenge}}
 +
===More Fun (Optional)===
 +
{{TestSuite|OptionalFunFibonacciTestSuite|fibonacci.fun}}
 +
 
 
==Performance==
 
==Performance==
{{Performance|FibonacciIterations|fibonacci.studio}}
+
{{Performance|FibonacciTiming|fibonacci.performance}}
 +
 
 +
{{Performance|FibonacciIterations|fibonacci.performance}}

Latest revision as of 02:03, 22 February 2023

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.

Ted Talk

Scientific American

Mathematics of Sunflowers

Fibonacci spiral.jpg


Code To Use

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)

For the required part of the studio, you will be implementing a Fibonacci calculator five different ways. Some will be in parallel, some won't. The goal for each is to simply have it return the nth Fibonacci number that is initially passed through

RecurrenceRelationSequentialFibonacciCalculator

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

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

The first file to complete is the basic recursive solution to Fibonacci. This should be done sequentially, and won't look too different from when you did it back in 131. Remember that instead of adding integers, we are using BigIntegers, so make sure to properly handle those.

recurrence relation

seed values

RecurrenceRelationParallelFibonacciCalculator

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

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

Now make the solution you just wrote parallel, such that fibonacci(n-1) and fibonacci(n-2) are being solved at the same time. Do this by using futures. Make sure to call future.get() at the right time so there is sufficient parallelism.

Attention niels epting.svg Warning:The parallelism tests assume that you limit your base cases to 0 and 1, so please do NOT add a base case for 2.

join vs future.get()

Attention niels epting.svg Warning:RecurrenceRelationParallelFibonacciCalculator.java does not contain the static import for join.

You can either include the static import:

import static fj.FJ.join;

and use join or

invoke future.get():

interface Future<V>.

get()

MemoizationSequentialFibonacciCalculator

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

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

The recurrence relation algorithm for Fibonacci has a lot of repeated calculations. For example, if we want fibonacci(10), we need to calculate fibonacci(9) and fibonacci(8), but during the calculations of fibonacci(9), we also calculate fibonacci(8), so that part is getting repeated. The bigger the number, the more repetition there is and the larger impact it has on our performance. The smart way to get around this is memoization. By storing our calculation results (in this case, with an array), we can simply refer to the work we've already done rather than doing it again.

Implement the recurrence relation algorithm again (sequentially), but employ memoization this time for the win. Make sure to store your work, and only do more work if it hasn't yet been done.

provided fibonacci method:

	@Override
	public BigInteger fibonacci(int n) {
		BigInteger[] memos = new BigInteger[n + 1];
		return fibonacciMemo(memos, n);
	}
Circle-information.svg Tip: you need not edit the fibonacci method. You should only need to edit the fibonacciMemo method.
Attention niels epting.svg Warning: Do NOT invoke fibonacci from fibonacciMemo. Invoke fibonacciMemo from fibonacciMemo.
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.

DynamicIterativeSequentialFibonacciCalculator

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

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

In the previous algortihms, we've been tackling this problem from the top-down. But that isn't always the easiest way to think about the problem. Imagine you are simply writing out Fibonacci numbers:

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

You (assuming you aren't a human super-computer) start from the very bottom, and keep working the sequence up to your answer.

Recall from the lecture where we described calculating each subsequent value based solely on the previous two.

Dynamic fibonacci slide.png slide

How would you go about converting this process into code? Note: it should be sequential, and not have any recursive calls.

Challenge (Optional)

LinearRecurrenceSequentialFibonacciCalculator

Work:

note: can be memoized to

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

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

Thanks to how awesome math is, we can actually solve the nth Fibonacci number without knowing those for n-1 and n-2. We have provided the algorithm below. It is your job to translate this into code. Keep it sequential.

Once you finish with this, make sure to go back and compare the performance speed of all five of these algorithms. The results are very thought-provoking!

recurrence relation

if n is odd
else


seed values

Attention niels epting.svg Warning: Do NOT invoke fibonacci(k) or fibonacci(k-1) multiple times if you can catch the result in a variable and reuse it.
Circle-information.svg 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.
Circle-information.svg Tip: You can shift left by 1 if you would prefer to not have to multiply by the big integer value of 2.

More Fun (Optional)

RecurrenceRelationParallelWithThresholdFibonacciCalculator

Similar to #RecurrenceRelationParallelFibonacciCalculator but with a predicate 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].

DynamicRecursiveSequentialFibonacciCalculator

RoundPhiToTheNOverSqrt5SequentialFibonacciCalculator

Testing Your Solution

Correctness

Studio (Required)

class: _FibonacciTestSuite.java Junit.png
package: fibonacci.exercise
source folder: testing/src/test/java

Challenge (Optional)

class: ChallengeFibonacciTestSuite.java Junit.png
package: fibonacci.challenge
source folder: testing/src/test/java

More Fun (Optional)

class: OptionalFunFibonacciTestSuite.java Junit.png
package: fibonacci.fun
source folder: testing/src/test/java

Performance

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