Class running Fibonacci
The Fibonacci algorithm can be coded many ways. This example shows Fibonacci implemented with the Streams interface. The student has challenge to use Inheritance and Polymorphism to produce multiple algorithms, but minimize code changed in original Class.
/*
* Creator: Nighthawk Coding Society
* Mini Lab Name: Fibonacci sequence, featuring a Stream Algorithm
*
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
/* Objective will require changing to abstract class with one or more abstract methods below */
public class Fibo {
String name; // name or title of method
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
ArrayList<Long> list; // captures current Fibonacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
long executionTime;
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public Fibo() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public Fibo(int nth) {
this.size = nth;
this.list = new ArrayList<>();
this.hashID = 0;
this.hash = new HashMap<>();
//initialize fibonacci and time mvc
this.init();
}
/*
This Method should be "abstract"
Leave method as protected, as it is only authorized to extender of the class
Make new class that extends and defines init()
Inside references within this class would change from this to super
Repeat process using for, while, recursion
*/
protected void init() {
final long startTime = System.nanoTime();
this.name = "Stream";
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
.limit(this.size)
.forEach(f -> this.setData(f[0]) );
this.executionTime = System.nanoTime() - startTime;
}
/*
Number is added to fibonacci sequence, current state of "list" is added to hash for hashID "num"
*/
public void setData(long num) {
list.add(num);
hash.put(this.hashID++, list.clone());
}
/*
Custom Getter to return last element in fibonacci sequence
*/
public long getNth() {
return list.get(this.size - 1);
}
/*
Custom Getter to return last fibonacci sequence in HashMap
*/
public Object getNthSeq(int i) {
return hash.get(i);
}
/*
Console/Terminal supported print method
*/
public void print() {
System.out.println("Init method = " + this.name);
System.out.println("fibonacci Number " + this.size + " = " + this.getNth());
System.out.println("fibonacci List = " + this.list);
System.out.println("fibonacci Hashmap = " + this.hash);
for (int i=0 ; i<this.size; i++ ) {
System.out.println("fibonacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
}
System.out.println("Init method runtime = " + this.executionTime);
}
// HACKS START HERE
// For-loop implementation
public class usingFor extends Fibo {
public usingFor() {
super(20);
}
public usingFor(int n) {
super(n);
}
@Override
protected void init() {
final long startTime = System.nanoTime();
this.name = "For";
long[] numbers = {0, 1};
for (int i = 0; i < this.size; i++) {
this.setData(numbers[0]);
numbers = new long[] {numbers[1], numbers[0] + numbers[1]};
}
this.executionTime = System.nanoTime() - startTime;
}
}
// While-loop implementation
public class usingWhile extends Fibo {
public usingWhile() {
super(20);
}
public usingWhile(int n) {
super(n);
}
@Override
protected void init() {
final long startTime = System.nanoTime();
this.name = "While";
long[] numbers = {0, 1};
int i = 0;
while (i < this.size) {
this.setData(numbers[0]);
numbers = new long[] {numbers[1], numbers[0] + numbers[1]};
i++;
}
this.executionTime = System.nanoTime() - startTime;
}
}
// Recursion impelmentation
public class usingRecursion extends Fibo {
public usingRecursion() {
super(20);
}
public usingRecursion(int n) {
super(n);
}
@Override
protected void init() {
final long startTime = System.nanoTime();
this.name = "Recursion";
int counter = 0;
long[] numbers = {0, 1};
increment(numbers, counter);
this.executionTime = System.nanoTime() - startTime;
}
public void increment(long[] numbers, int counter) {
this.setData(numbers[0]);
if (counter < this.size - 1) {
numbers = new long[] {numbers[1], numbers[0] + numbers[1]};
increment(numbers, counter + 1);
}
}
}
/*
Tester class method. If this becomes abstract you will not be able to test it directly ...
Change this method to call "main" class of each of the extended classes
*/
public static void main(String[] args) {
Fibo fib = new Fibo();
fib.print();
Fibo.usingFor test1 = fib.new usingFor();
test1.print();
Fibo.usingWhile test2 = fib.new usingWhile();
test2.print();
Fibo.usingRecursion test3 = fib.new usingRecursion();
test3.print();
}
}
Fibo.main(null);
Hacks
Objective of Hacks is to produce the Fibonacci sequence in multiple ways. See this runtime. The method provided is Stream, the objective is to produce more familiar methods like ...- For Loop
- While Loop
- Recursion The trick is to produce all these methods without reproducing the same lines of code. Try to store and capture result data from parent class.
- Read the comments of the code in this Blog, as the code instructs you on what to abstract.
In Blog or code, comment on how this assignment fulfills the following standards from College Board.
- Skill 1.B:Determine code that would be used to complete code segments (ie For, While, Recursion)- Skill 4.C: Determine if two or more code segments yield equivalent results (be sure to Discuss how you know results are the same)
- Skill 5.A: Describe the behavior of a given segment of program code (describe the difference in recursion versus for & while loops, perhaps add timing to determine speed)
Personal Hacks: Lesson 5
The previous algorithm already showed how to make the Fibonacci sequence using a Stream algorithm. However, there are numerous other ways to make the fibonacci sequence, whether it be through for-loops, while-loops, or recursion.
To avoid rewriting code, I put all of my hacks in the previous code cell, so I could access the attributes and methods already created in Fibo, making everything a lot easier to implement. Things like the hashmap along with the setData() function made everything a lot simpler.
Note that I did edit the print section to output the execution time, but I'll get into why I did that in this next section.
College Board Standards
- Skill 1.B: For this particular problem, I created three different implementations (alongside the premade one). Using for-loops and while-loops had pretty similar implementations. Both had a line at the top that handled the iteration, and in the case of the while-loop, I just needed to increment the counter at the bottom (whereas the for-loop was automatic). For Recursion, I had to call a function over and over again with a counter that incremented with each call of the function to make sure the sequence stopped at the right number.
- Skill 4.C: The Stream, For-loop, While-loop, and Recursion implementations of the Fibonacci sequence all yield the same results. I can tell this by comparing the printed results from each method - all of them are exactly the same (save for the names of the init method used).
- Skill 5.A: For the most part, it appears that, For-loop, While-loop, and Recursion implementations take roughly the same amount of time, hovering around ~13500 nanoseconds of execution time. However, the Stream method seems to take significantly more amounts of time, spending 324375 nanoseconds, which is about 24 times longer than the previous implementations mentioned. In order to find these numbers, I used System.nanoTime(), which basically returns the System time in nanoseconds. Simply subtracting the difference between the start and end implementation allowed me to determine how long it took for each method to run.