Fibonacci
coding fibonacci in different ways
/*
* 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
/*
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() {
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]) );
}
/*
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));
}
}
/*
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
*/
static public void main(String[] args) {
Fibo fib = new Fibo();
fib.print();
}
}
Fibo.main(null);
/*
* 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
double duration;
/*
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
double startTime = System.nanoTime();
this.init();
double endTime = System.nanoTime();
this.duration = ((endTime - startTime));
}
class FiboRecursion extends Fibo {
// default constructor
public FiboRecursion() {
super();
}
// takes input of number, calls constructor
public FiboRecursion(int n) {
super(n);
}
// the recursive function: type int so it feeds into self and returns a value
public int fibNum(int n)
{
// if its the first 2 terms (0 or 1), set the data in the array and hashmap as 0 or 1 and return
if (n <= 1) {
this.setDataRec(n, n); // setData as 0 or 1
return n;
}
int currentFibNum = fibNum(n-1) + fibNum(n-2); // sets the current fibonacci number to the sum of the previous two (recursion starts)
this.setDataRec(n, currentFibNum); // sets data of the currentFibNum to the index of the fibNum (n)
return currentFibNum; // returns for recursion
}
@Override // overwrite init function for the RECURSION
protected void init() {
// set name
super.name = "recursion";
// populate array
for (int i = 0; i < super.size; i++) {
super.list.add((long) 0);
super.hash.put(i, super.list.clone());
}
// find the fib num up to super.size minus 1 because does not include
fibNum(super.size - 1);
}
// better setdata: can put into specific index
public void setDataRec(int n, long num) {
super.list.set(n, num); // sets something into the array at certain index
ArrayList<Long> smallList = new ArrayList<Long>(super.list.subList(0,n+1)); // cuts off the list at the fibonacci number length, as it already populates with the amount needed
super.hash.put(n, smallList.clone()); // adds the list to hashmap
}
}
// extending for WHILE
class FiboWhile extends Fibo {
// calls super constructor default
public FiboWhile() {
super();
}
// constructor with input
public FiboWhile(int n) {
super(n);
}
@Override // override old init
protected void init() {
super.name = "while"; //name
// initializes variables for first terms of fibo
int previousTerm = 0, currentTerm = 1;
// initiate variable for while loop
int i = 1;
while (i <= super.size) {
// setData as the previous term
super.setData(previousTerm);
// nextTerm is the previous 2 terms added
int nextTerm = previousTerm + currentTerm;
// update the two old terms to move one up the fibo sequence
previousTerm = currentTerm;
currentTerm = nextTerm;
// repeat
i++;
}
}
}
// extending for FOR
class FiboFor extends Fibo {
// constructor
public FiboFor() {
super();
}
// constructor with input
public FiboFor(int n) {
super(n);
}
// overrides init for FOR
@Override
protected void init() {
super.name = "for";
// initializes variables for first 2 terms
int previousTerm = 0, currentTerm = 1;
for (int i = 1; i <= super.size; i++) {
// in essence same code as while, but more concise
super.setData(previousTerm);
int nextTerm = previousTerm + currentTerm;
// shift the terms up one in sequence
previousTerm = currentTerm;
currentTerm = nextTerm;
}
}
}
/*
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() {
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]) );
}
/*
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("time taken = " + this.duration/1000000 + " ms");
}
// inspiration from https://stackoverflow.com/a/5503239
public static boolean areSame(long value, long... values) {
for (long i: values) if(value != i) return false;
return true;
}
/*
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
*/
static public void main(String[] args) {
// prints for all types
Fibo fib = new Fibo();
fib.print();
System.out.println();
FiboFor fibFor = fib.new FiboFor();
fibFor.print();
System.out.println();
FiboWhile fibWhile = fib.new FiboWhile();
fibWhile.print();
System.out.println();
FiboRecursion fibRecursion = fib.new FiboRecursion();
fibRecursion.print();
if (Fibo.areSame(fib.getNth(), fibFor.getNth(), fibRecursion.getNth(), fibWhile.getNth())) {
System.out.println("all values are equal: " + fib.getNth());
}
}
}
Fibo.main(null);
// extending for FOR
class FiboFor extends Fibo {
// constructor
public FiboFor() {
super();
}
// constructor with input
public FiboFor(int n) {
super(n);
}
// overrides init for FOR
@Override
protected void init() {
super.name = "for";
// initializes variables for first 2 terms
int previousTerm = 0, currentTerm = 1;
for (int i = 1; i <= super.size; i++) {
// in essence same code as while, but more concise
super.setData(previousTerm);
int nextTerm = previousTerm + currentTerm;
// shift the terms up one in sequence
previousTerm = currentTerm;
currentTerm = nextTerm;
}
}
}
Skill 1.B
In essence, the for overrides the init function. It then implements a for loop, which adds the previous 2 terms as many times as the nth number of the fibonacci sequence, then stops. It uses the super to call the parent constructor, as well as set values for the name. It also calls super.setData using the super.
// extending for WHILE
class FiboWhile extends Fibo {
// calls super constructor default
public FiboWhile() {
super();
}
// constructor with input
public FiboWhile(int n) {
super(n);
}
@Override // override old init
protected void init() {
super.name = "while"; //name
// initializes variables for first terms of fibo
int previousTerm = 0, currentTerm = 1;
// initiate variable for while loop
int i = 1;
while (i <= super.size) {
// setData as the previous term
super.setData(previousTerm);
// nextTerm is the previous 2 terms added
int nextTerm = previousTerm + currentTerm;
// update the two old terms to move one up the fibo sequence
previousTerm = currentTerm;
currentTerm = nextTerm;
// repeat
i++;
}
}
}
Skill 1.B
Almost the same thing as the for loop, except the variable of i is defined outside the loop. It also uses super. It's slightly slower, possibly due to the initialization of the variable out of the iteration.
class FiboRecursion extends Fibo {
// default constructor
public FiboRecursion() {
super();
}
// takes input of number, calls constructor
public FiboRecursion(int n) {
super(n);
}
// the recursive function: type int so it feeds into self and returns a value
public int fibNum(int n)
{
// if its the first 2 terms (0 or 1), set the data in the array and hashmap as 0 or 1 and return
if (n <= 1) {
this.setDataRec(n, n); // setData as 0 or 1
return n;
}
int currentFibNum = fibNum(n-1) + fibNum(n-2); // sets the current fibonacci number to the sum of the previous two (recursion starts)
this.setDataRec(n, currentFibNum); // sets data of the currentFibNum to the index of the fibNum (n)
return currentFibNum; // returns for recursion
}
@Override // overwrite init function for the RECURSION
protected void init() {
// set name
super.name = "recursion";
// populate array
for (int i = 0; i < super.size; i++) {
super.list.add((long) 0);
super.hash.put(i, super.list.clone());
}
// find the fib num up to super.size minus 1 because does not include
fibNum(super.size - 1);
}
// better setdata: can put into specific index
public void setDataRec(int n, long num) {
super.list.set(n, num); // sets something into the array at certain index
ArrayList<Long> smallList = new ArrayList<Long>(super.list.subList(0,n+1)); // cuts off the list at the fibonacci number length, as it already populates with the amount needed
super.hash.put(n, smallList.clone()); // adds the list to hashmap
}
}
Skill 1.B
This one was the most intensive, especially as adding data into the predefined ArrayList and HashMap proved to be quite difficult. In specific, the recursion required things to be added into the array out of order, so I could not rely on the setData method. However, I could also not just add data into any index in the ArrayList, because I couldn't add data into an empty Array, only add or append to it. So, I had to first loop through how many fibonacci numbers were going to get calculated and add placeholder values to both the ArrayList and the HashMap. Then, I had to create a new method to set the data into a specific index, as seen above. It has to truncate the ArrayList as the placeholder values stay beyond the Fibonacci value calculated.
The recursion itself wasn't that complicated: if it was either 1 or 0, it would just return 1 and 0 to the respective fibonacci number. When you call a specific number, it sets the fibonacci number for the previous two added together, which calls it again and recurses upon itself.
Skill 5.A
Recursion is much slower, though, as all these function calls cannot complete until it recurses onto the 0th Fibonacci number, then executing back all the way up the heap. This extreme use of memory, as well as having to call the function twice every time it runs, leads to slower execution than iteration. This is seen by the time taken increasing as well.
// inspiration from https://stackoverflow.com/a/5503239
public static boolean areSame(long value, long... values) {
for (long i: values) if(value != i) return false;
return true;
}
Skill 4.C
This code takes one value to check against, then a list of other values to check if they are all the same. This took inspiration from a stackexchange answer. A variable takes on the value of all the rest of the values, and an if statement checks if those values are equal to the original. If it is, it will return true, and in my program it tells you that it is true.