hi all I'm trying to build a couple of algorithms here for, my advanced data structures course and get the run times however I cant seem to get the clock_t variables to output to the screen at all. check the code
the problem is located in the first loop in the main. Every time I output the variable duration to the screen it shows up as zero. I did a debug on it and according that it shows a value for start and finish. So what is the deal here.Code:
#include<iostream>
#include<fstream>
#include<iomanip>
#include <time.h>
using namespace std;
/**************************************************************
PURPOSE:
The algorithm works iterativley it takes an input n it
then calculates the fibonacci sequence up to that number
by adding LastButOne's values and lastValue over and
over again until the value of "i" is equal to that of
the value of "n". At this point the loop terminates
and no longer calculates any more numbers in
the fibonacci series. Since the algorithm is
being increased by a constant value the growth rate for
this algorithm is Big O(N)
IteratFib
DATA TABLE:
n = input for the function to calculate up to the nth fibonacci
LastValue = the F(n-1) value to be added
lastButone = the F(n-2) value to be added
i = The current number to be calculated starting at 2
counter = the number of iterations required to complete
answer = the actual calculation of the nth fibonacci number
start = a clock t variable to start the timer in each iteration of both
algorithms
finish = a clock t variable to get the end time of each iteration
/***************************************************************/
double IteratFib(double n, double &counter )
{
double answer;
if( n == 0 || n == 1 )
return n;
else
{
double lastButOne = 0;
double lastValue = 1;
//for loop to take n and compare it the
//variable j. If j is less than that number
//the loop then iterates and adds makes the
//variable answer equal to LastButOne + lastValue
//it then makes LastButone = Last Value or
//the Fn-2 it then makes lastValue = Currnent
//or Fn-1. These values are saved in each of
//these variables to calculate the Fn Fibonacci
//number for. It will do this until "n" is
//greater than "i". It then exits the loop
//and returns the calculated value of the nth
//Fibonacci number The loop will do this u
//the requested fibonacci number
for( int i = 2; i <= n; i++ )
{
answer = lastButOne + lastValue;
lastButOne = lastValue;
lastValue = answer;
counter++;
}
}
return answer;
}
/****************************************************************
PURPOSE:
this is the second version of the fibonacci series
calculation. This is the recursive version of the
program. This function is designed to go up to the
nth value which in shis case is 128. The implementation
of the program works by solving two previous instances of
itself. In this case it is the previous two numbers that
are two be added to equal the current fibonacci number.
For instance if you would like the fifth fibonacci number
it would be obtained by calculating 0,1,1,2,3. So in
essence the fifth fibonacci number is obtained by adding
the 3rd and the 4th numbers in that series. So the problem
doubles each time it is called and you end up with a growth
rate that is Big O(2^n) power or an exponential growth rate.
fibonacci()
DATA TABLE:
num = the value that is being used as the base case
count = the number of iterations for the function
/******************************************************************/
double fibonacci(double num, double &counter)
{
counter++;
//The first if statement is the base case for this program
//which checks to see if the number entering the algorithm
//is either one or zero. If it is either value it will then
//return that number since the Fibonacci of one or zero is
//itself. This is the case that will terminate the recusive
//calls back to the algorithm.
if(num==0 || num ==1)
{
counter++;
return num;
}
//the other case is if the number is greater than zero or one
//it then returns the number minus + the number minus two or
//the Fn = Fn-1 + Fn-2.
else
{
return fibonacci(num - 1, counter) + fibonacci(num - 2, counter);
}
}
void main()
{
/******************************************************************
main
DATA TABLE:
j = variable being used to determine whether the nth fib
counter = the number of iterations that are required for each
iteratOut = an ofstream variable to output to text file name "iterout.txt"
outfile = an ofstream variable to output to text file named "outfile.txt"
m = this variable is to store the calculation of "fibonacci"
temp = this variable is to store temporary variables when the user enters
a one to start the series of both algorithms
*******************************************************************/
ofstream outfile;
outfile.open("output.xls", ios::out);
ofstream iteratOut;
iteratOut.open("iteratData.xls", ios::out);
double m;
double counter = 0;
int temp;
clock_t start, finish;
double duration;
cout<<"This is the iterative version of the Fibonacci Calculation: "<<endl;
cout<<endl<<endl;
cout<<"Enter '1' to begin: "<<endl;
cout<<"From 1-128: "<<endl<<endl;
cin>>temp;
if(temp!=1)
temp=1;
//this first for loop is designed to start at 1 and
//go up to the 128th fibonacci number using an
//iterative fibonacci calculation
for (double j=1; j<=128; j++)
{
//initialize counter to zero
cout<< "F(" << j << ") = " <<setw(20)<<setiosflags(ios::left);
start=clock();
m=IteratFib(j,counter);
finish=clock();
duration = (double)(finish - start)/CLK_TCK;
//output the result of the nth fibonacci number
cout << fixed<<setprecision(2)<<m;
//output that to the screen as well as the counter
cout << "\t" << counter <<" Time elapsed : ";
cout <<duration<< "\n";
//now output those countents to the file
iteratOut << "F("<<j<< ")=" <<setw(20)<<setiosflags(ios::left);
iteratOut << fixed<<setprecision(2)<<m;
iteratOut << "\t" << counter << "\t"<<duration<<"\n";
counter=0;
}
//close text file
iteratOut.close();
cout <<endl<<endl;
//output to screen
cout << "This is the Recursive version of fibonacci: "<< endl;
//output to file
outfile << "RUN TIME AND ANALYSIS OF A RECURSIVE FIBONACCI ALGORITHM"
<< endl;
outfile << "FROM 1 TO 128"<<endl;
cout << "Enter '1' to begin: ";
//request user to start the sequence of in the recursive version fibonacci()
cin >> j;
//if else statement user enters something other than 1
if(j!=1)
j=1;
else
{
while(j<=128)
{ //initialize counter to zero for next iteration
counter=0;
//make "m" the value of the nth fibonacci
m=fibonacci(j, counter);
//output that value to the screen
cout <<"The fibonacci of "<<setprecision(0)<<fixed<<j<<" is "<<m <<endl;
//output the number of calls required to do recursive algorithm
cout <<"The total number of recursive calls to achieve fibonacci of "
<< counter <<" is " <<counter<<endl;
//output the value and the number of iterations
outfile <<"F("<<j<<")= "<<m<<"\t"
<<"ITERATIONS"<<"\t"<<counter<<endl;
//add one to "j" and get the next version of fibonacci
++j;
}
}
//close output file
outfile.close();
//end programs
}
