Timed Fibonacci Numbers
public class TimedFibonacci extends Array
{
/*Class TimedFibonacci implements the Fibonacci function both Recursivly,
Iteratively, and using a table so one can compare the efficiency of
the three methods.
*/
public TimedFibonacci()
{
/*Parameters NONE
Initialize the counters for all functions to 0.
These counters are used to keep track of how many calculations
were made inside each function.
The counter variables are only increased if calculating a Fibonacci
value greater than 2. This is because Fib(0) and Fib(1) are
constants and need no calculations.
*/
counterR = 0; /*used for RecursiveFib*/
counterL = 0; /*used for LoopFib*/
counterD = 0; /*used for DynamicFib*/
}
public int RecursiveFib(int f)
{
/*Parameter int f : f is the Fibonacci number to calculate.
It is assumed to be non-negative (no check made).
It calculates the Fibonacci value by making a recursive calls to
calculate f(n-1) and f(n-2).
Return: the answer to Fibonacci of f.
*/
if(f<=1) /*base case*/
return f;
else
{ counterR++; /*global var to determine # of calculations made*/
return RecursiveFib(f-1) + RecursiveFib(f-2);
}
}/*end RecursiveFib*/
public int LoopFib(int f)
{ /*Parameter int f : f is the Fibonacci number to calculate.
Uses an iterative loop to calculate the fibonacci values.
Bottom up approach.
Return: the answer to Fibonacci of f.
*/
int solution = 0; /*the most recent Fib value calculated.*/
int temp = 0; /*a temp varible used for swapping*/
if (f <= 1)
return f;
else
{ int F0 = 0;
int F1 = 1;
for(int i=2; i<=f; i++)
{ counterL = counterL + 1;
solution = F0 + F1;
temp = F1;
F1 = solution;
F0 = temp;
}/*end for*/
}
return solution;
}/*end LoopFib*/
public float ComputeFib(int F)
{ /*Parameter int f : f is the Fibonacci number to calculate.
Use a memory function DynamicFib to calculate Fibonacci values.
Return: the answer to Fibonacci of f.
*/
Array table = new Array(F+1);
return DynamicFib(F,table);
}/*end ComputeFib*/
public float DynamicFib(int F,Array table)
{ /*Parameter int F : The Fibonacci number to be calculated.
Parameter Array table : The memory table used to store previously
calculated Fibonacci values.
To calculate a Fibonacci value, look in the table to see if the
value has already been calculated, if so return the value in the
table, else call DynamicFib with the parameter necessary to fill
the empty index in the table. Once a Fibonacci value is found
that was not previously in the table, store the value in the table
for future use.
Return: the solution for Fibonacci(F).
*/
float solution = 0;
if (!table.IsPositionEmpty(F))
return table.FindPosition(F);
else
{ if (F <=1)
{ table.AddElement(F,F);
return F;
}
else
{ counterD++;
solution = DynamicFib(F-1,table) + DynamicFib(F-2,table);
table.AddElement(solution,F);
return solution;
}
}/*end else if element not in memory table*/
}/*end DynamicFib*/
public static void main(String[] args)
{
TimedFibonacci f1 = new TimedFibonacci();
int solutionR = 0; /*solution to Recursive Fib*/
int solutionL = 0; /*solution to Loop Fib*/
float solutionD = 0; /*solution to MemFunction Fib*/
long begin,end;
long timeR,timeD,timeL;
begin = System.currentTimeMillis();
solutionR = f1.RecursiveFib(10);
end = System.currentTimeMillis();
timeR = end-begin;
begin = System.currentTimeMillis();
solutionL = f1.LoopFib(10);
end = System.currentTimeMillis();
timeL = end-begin;
begin = System.currentTimeMillis();
solutionD = f1.ComputeFib(10);
end = System.currentTimeMillis();
timeD = end-begin;
if (solutionR == solutionD && solutionR == solutionL)
/*functions worked*/
{ System.out.print("The Solution to Fib(10) is: ");
System.out.println(solutionR);
System.out.println();
System.out.println("Here is the data for calculating Fibonacci(10):");
System.out.println();
System.out.print("The Recursive Function made ");
System.out.print(f1.counterR);
System.out.print(" calculations");
System.out.println(" and took " + timeR + " milliseconds.");
System.out.print("The Iterative Function made ");
System.out.print(f1.counterL);
System.out.print(" calculations");
System.out.println(" and took " + timeL + " milliseconds.");
System.out.print("The Memory Function made ");
System.out.print(f1.counterD);
System.out.print(" calculations");
System.out.println(" and took " + timeD + " milliseconds.");
System.out.println();
}
else System.out.println("There is an error in the Fib functions.");
TimedFibonacci f2 = new TimedFibonacci();
begin = System.currentTimeMillis();
solutionR = f2.RecursiveFib(20);
end = System.currentTimeMillis();
timeR = end-begin;
begin = System.currentTimeMillis();
solutionL = f2.LoopFib(20);
end = System.currentTimeMillis();
timeL = end-begin;
begin = System.currentTimeMillis();
solutionD = f2.ComputeFib(20);
end = System.currentTimeMillis();
timeD = end-begin;
if (solutionR == solutionD && solutionR == solutionL) /*functions worked*/
{ System.out.print("The Solution to Fib(20) is: ");
System.out.println(solutionR);
System.out.println();
System.out.println("Here is the data for calculating Fibonacci(20):");
System.out.println();
System.out.print("The Recursive Function made ");
System.out.print(f2.counterR);
System.out.print(" calculations");
System.out.println(" and took " + timeR + " milliseconds.");
System.out.print("The Iterative Function made ");
System.out.print(f2.counterL);
System.out.print(" calculations");
System.out.println(" and took " + timeL + " milliseconds.");
System.out.print("The Memory Function made ");
System.out.print(f2.counterD);
System.out.print(" calculations");
System.out.println(" and took " + timeD + " milliseconds.");
System.out.println();
}
else System.out.println("There is an error in the Fib functions.");
TimedFibonacci f3 = new TimedFibonacci();
begin = System.currentTimeMillis();
solutionR = f3.RecursiveFib(30);
end = System.currentTimeMillis();
timeR = end-begin;
begin = System.currentTimeMillis();
solutionL = f3.LoopFib(30);
end = System.currentTimeMillis();
timeL = end-begin;
begin = System.currentTimeMillis();
solutionD = f3.ComputeFib(30);
end = System.currentTimeMillis();
timeD = end-begin;
if (solutionR == solutionD && solutionR == solutionL) /*functions worked*/
{ System.out.print("The Solution to Fib(30) is: ");
System.out.println(solutionR);
System.out.println();
System.out.println("Here is the data for calculating Fibonacci(30):");
System.out.println();
System.out.print("The Recursive Function made ");
System.out.print(f3.counterR);
System.out.print(" calculations");
System.out.println(" and took " + timeR + " milliseconds.");
System.out.print("The Iterative Function made ");
System.out.print(f3.counterL);
System.out.print(" calculations");
System.out.println(" and took " + timeL + " milliseconds.");
System.out.print("The Memory Function made ");
System.out.print(f3.counterD);
System.out.print(" calculations");
System.out.println(" and took " + timeD + " milliseconds.");
System.out.println();
}
else System.out.println("There is an error in the Fib functions.");
}/*end main*/
private int counterD;
private int counterR;
private int counterL;
}/*end class TimedFibonacci*/
-----------------------------------------------------------------------------------------
/* Here is a separate class called "Array" which I used in the above code
* You must put this in a separate file called "Array.java", compile it,
* and have the "Array.class" file in the same directory as the above
*/
class Array
{
public Array()
{
/*if no parameters are passed to class Array, then the default
array size is 10. The indicies range from 0-9.
*/
this(10);
}
public Array(int size)
{
/*Parameter int size is the size of the created array.
The indicies of the array ranges from 0-(size-1).
All of the positions in the array are initialized to empty.
Returned : nothing.
*/
Arraysize = size;
List = new float[size];
for (int i = 0; i < Arraysize; i++)
List[i] = -1;
}
public boolean IsEmpty()
{
/* Return true if the array is empty or false if array not empty.
*/
for (int i=0; i= 0 && position < Arraysize)
return List[position] == -1;
else return false;
}
public boolean AddElement(float element,int position)
{
/* Parameter element is the element to add to the array.
Parameter position is the index location in the array
where the element is to be added.
Insert the element at the given position if the position
is not already occupied.
Return true if the element successfully added.
Return false if the position was already occupied or if position
was out of the array range.
*/
if ( IsPositionEmpty(position))
{ List[position] = element;
return true;
}
else return false;
}
public void ReplaceElement(float element,int position)
{
/* Parameter element is the element to add to the array.
Parameter position is the index location in the array
where the element is to be added.
Insert the element at the given position reguarless if the position
is already occupied.
Return Nothing
*/
List[position] = element;
}
public float DeleteElement(int position)
{
/* Parameter position is the index value of the array
where the element will be deleted.
Delete the element indicated by position if position is
not out of the range of the array.
Return the value of array[position] before element deleted.
Return -1 if the position was out of range.
*/
if (position >= 0 && position < Arraysize)
{ float element = List[position];
List[position] = -1;
return element;
}
else return -1;
}
public int FindElement(float element)
{
/* Parameter element is the value to be found in the array.
Return the position of the element if element found.
Return -1 if the element is not found.
*/
for (int i=0; i < Arraysize ; i++)
if (List[i] == element)
return i; /*index position where element found*/
return -1; /*element not found*/
}
public float FindPosition(int position)
{
/*Parameter position is the index into the array.
Return the element found in array[position] if position is
a valid array index.
Return -1 if position is an invalid array index.
*/
if (position >= 0 && position < Arraysize)
return List[position];
else return -1; /*position out of range of the array*/
}
public int SizeOf()
{
/* Return the size of the array */
return Arraysize;
}
public void PrintList()
{
/*Print the elements in the list in ascending order 0-Arraysize.
*/
for(int i = 0; i < Arraysize; i++)
{ System.out.print("The element in position ");
System.out.print(i);
System.out.print("is ");
System.out.println(List[i]);
}
}
private int Arraysize; /*The size of the array*/
public float [] List; /*The actual array*/
}/*end class Array*/