Chapter 5, Problem 1PA

Program Plan Intro

Program Plan:

• In function “meanIterative()”:
  • Compute sum of array elements using a “for” loop.
  • Compute mean by dividing sum with number of elements in array.
• In function “varianceIterative()”:
  • Compute sum of square of difference between each element with mean.
  • Compute variance by dividing it with “n-1”.
• In function “meanRecursive()”:
  • If starting index “ii” is same as “n-1”, return element divided by “n”.
  • Otherwise, increment the value “ii” by “1” and compute mean all numbers in array by calling function recursively.
• In function “varianceRecursive()”:
  • If starting index “ii” is same as “n-1”, return variance of that element.
  • Otherwise, increment the value “ii” by “1” and compute variance all numbers in array by calling function recursively.
• In “main()” function:
  • Create random input arrays of size “500”, “1000”, “1500” and “2000”.
  • For each input array compute standard deviation by using both iterative and recursive functions.
  • Compute running time for both and compare each other.

Program Description Answer

/**********************************************************

* Program to compare running time to compute standard    *

* deviation of different sized samples using iterative   *

* and recursive functions.                               *

**********************************************************/

Explanation of Solution

Program:

//Include header files

#include<iostream>

#include<ctime>

using namespace std;

//Iterative function to compute mean of n numbers

double meanIterative(int data[], int n)

{

  //Declare variable

  double mean;

  //Initialize summ as 0

  int summ=0;

  //Each number from array

  for (int i = 0; i < n; i++)

  {

  //Add number with summ

  summ = summ + data[i];

  }

  //Compute mean of numbers

  mean =(double) summ / (double)n;

  //Return mean

  return mean;

}

//Iterative function to compute variance of n numbers

double varianceIterative(int data[], int n, double mean)

{

  //Declare variable

  double varianc;

  //Initialize summm as 0

  double summm=0;

  //Each number from array

  for (int i = 0; i < n; i++)

  {

  //Add number with summm

  summm = summm + pow((data[i] - mean), 2);

  }

  //Compute variance

  varianc = summm / (float)(n-1);

  //Return variance

  return varianc;

}

//Recursive function to compute mean of n numbers

double meanRecursive(int data[], int ii,int n)

{

  //If starting index ii is equal to n

  if (ii == n-1)

  //Return mean of that number

  return (double)data[ii]/(double)n; 

/*Otherwise increment value of ii by 1 and compute mean of numbers by calling function itself recursively*/

return (double)data[ii]/(double)n +meanRecursive(data, ii + 1, n); 

}

//Recursive function to compute variance of n numbers

double varianceRecursive(int data[], int ii,int n, double mean)

{

  //If starting index ii is equal to n

  if (ii == n-1)

  //Return variance of that number

  return pow((double)data[ii]-mean,2)/(double)(n-1); 

/*Otherwise increment value of ii by 1 and compute variance of numbers by calling function itself recursively*/

return pow((double)data[ii]-mean,2)/(double)(n-1) +varianceRecursive(data, ii + 1, n, mean); 

}

//Program begins with main() function

int main()

{

//Declare variables

int data_500_S[500],data_1000_S[1000],data_1500_S[1500],data_2000_S[2000];

srand((unsigned)time(0));

//For each index of array of size 500

for(int ii=0;ii<500;ii++)

{

/*Compute random number and store it into array index*/

  data_500_S[ii] = rand() % 10000;

  }

  //For each index of array of size 1000

  for(int ii=0;ii<1000;ii++)

  {

/*Compute random number and store it into array index*/

  data_1000_S[ii] = rand() % 10000;

  }

  for(int ii=0;ii<1500;ii++)

  {

/*Compute random number and store it into array index*/

  data_1500_S[ii] = rand() % 10000;

  }

  for(int ii=0;ii<2000;ii++)

  {

/*Compute random number and store it into array index*/

data_2000_S[ii] = rand() % 10000;

}

  //Declare variables

double meeanIte, varianceIte,standarddevIte,meeanRec, varianceRecu,standarddevRecu ;

  //For array input of size 500

  cout<<"For n=500: \n"<<endl;

  //Capture current time and store it as initial time

  double start_s=clock();

/*Call iterative function to compute mean of array elements*/

meeanIte=meanIterative(data_500_S, 500);

cout<<"Mean using Iterative function is: "<<meeanIte<<endl;

/*Call iterative function to compute variance of array elements*/

varianceIte=varianceIterative(data_500_S, 500,meeanIte);

cout<<"Variance using Iterative function is: "<<varianceIte<<endl;

//Compute standard deviation using iterative functions

standarddevIte=sqrt(varianceIte);

cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;

//Capture current time and store it as stop time

double stop_s=clock();

//Compute running time in by using start and end time

cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;

  //Capture current time and store it as initial time

  start_s=clock();

/*Call recursive function to find mean of array elements*/

meeanRec=meanRecursive(data_500_S, 0,500);

cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;

/*Call recursive function to find variance of array elements*/

varianceRecu=varianceRecursive(data_500_S, 0,500,meeanRec);

cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;

//Compute standard deviation using recursive functions

standarddevRecu=sqrt(varianceRecu);

cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;

//Capture current time and store it as stop time

stop_s=clock();

cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;

//For array input of size 1000

cout<<"\n For n=1000: \n"<<endl;

//Capture current time and store it as initial time

start_s=clock();

/*Call iterative function to compute mean of array elements*/

  meeanIte=meanIterative(data_1000_S, 1000);

cout<<"Mean using Iterative function is: "<<meeanIte<<endl;

/*Call iterative function to compute variance of array elements*/

varianceIte=varianceIterative(data_1000_S, 1000,meeanIte);

cout<<"Variance using Iterative function is: "<<varianceIte<<endl;

//Compute standard deviation using iterative functions

standarddevIte=sqrt(varianceIte);

cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;

  //Capture current time and store it as stop time

  stop_s=clock();

  //Compute ruuning time in by using start and end time

cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;

//Capture current time and store it as initial time

start_s=clock();

/*Call recursive function to find mean of array elements*/

  meeanRec=meanRecursive(data_1000_S, 0,1000);

cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;

/*Call recursive function to find variance of array elements*/

varianceRecu=varianceRecursive(data_1000_S, 0,1000,meeanRec);

cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;

//Compute standard deviation using recursive functions

standarddevRecu=sqrt(varianceRecu);

cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;

//Capture current time and store it as stop time

  stop_s=clock();

  //Compute running time in by using start and end time

cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;

//For array input of size 500

cout<<"\n For n=1500: \n"<<endl;

//Capture current time and store it as start time

start_s=clock();

/*Call iterative function to compute mean of array elements*/

meeanIte=meanIterative(data_1500_S, 1500);

cout<<"Mean using Iterative function is: "<<meeanIte<<endl;

/*Call iterative function to compute variance of array elements*/

varianceIte=varianceIterative(data_1500_S, 1500,meeanIte);

cout<<"Variance using Iterative function is: "<<varianceIte<<endl;

  //Compute standard deviation using iterative functions

  standarddevIte=sqrt(varianceIte);

cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;

//Capture current time and store it as stop time

stop_s=clock();

//Compute running time in by using start and end time

cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << " Milli seconds"<<endl;

//Capture current time and store it as start time

start_s=clock();

/*Call recursive function to find mean of array elements*/

  meeanRec=meanRecursive(data_1500_S, 0,1500);

cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;

/*Call recursive function to find variance of array elements*/

varianceRecu=varianceRecursive(data_1500_S, 0,1500,meeanRec);

cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;

//Compute standard deviation using recursive functions

standarddevRecu=sqrt(varianceRecu);

cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;

//Capture current time and store it as stop time

stop_s=clock();

//Compute running time in by using start and end time

cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;

//For array input of size 500

cout<<"\n For n=2000: \n"<<endl;

//Capture current time and store it as start time

start_s=clock();

/*Call iterative function to compute mean of array elements*/

meeanIte=meanIterative(data_2000_S, 2000);

cout<<"Mean using Iterative function is: "<<meeanIte<<endl;

/*Call iterative function to compute variance of array elements*/

varianceIte=varianceIterative(data_2000_S, 2000,meeanIte);

cout<<"Variance using Iterative function is: "<<varianceIte<<endl;

  //Compute standard deviation using iterative functions

  standarddevIte=sqrt(varianceIte);

cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;

//Capture current time and store it as stop time

stop_s=clock();

//Compute running time in by using start and end time

cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli Seconds"<<endl;

  //Capture current time and store it as start time

  start_s=clock();

/*Call recursive function to find mean of array elements*/

meeanRec=meanRecursive(data_2000_S, 0,2000);

cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;

/*Call recursive function to find variance of array elements*/

varianceRecu=varianceRecursive(data_2000_S, 0,2000,meeanRec);

cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;

//Compute standard deviation using recursive functions

standarddevRecu=sqrt(varianceRecu);

cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;

//Capture current time and store it as stop time

  stop_s=clock();

  //Compute running time in by using start and end time

cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli Seconds"<<endl;

  //Return from program

  system("pause");

  return 0;

}

Comparison:

Input array size, n	Running time in Milliseconds
	Iterative Method	Recursive method
500	17	14
1000	9	6
1500	7	7
2000	7	7

Conclusion:

• Running time for input array of size “n” equals “500” is larger for iterative method than recursive method.
• For other input arrays the running time for both iterative and recursive are almost similar or sometimes it varies for small values.

Sample Output

Output:

For n=500:

Mean using Iterative function is: 4394.44

Variance using Iterative function is: 8.22268e+006

Standard deviation using Iterative function is: 2867.52

Running time for iterative function: 17 Milli seconds

 Mean using Recursive function is: 4394.44

Variation using Recursive function is: 8.22268e+006

Standard deviation using Recursive function is: 2867.52

Running time for Recursive function: 14 Milli seconds

 For n=1000:

Mean using Iterative function is: 4908.97

Variance using Iterative function is: 8.77065e+006

Standard deviation using Iterative function is: 2961.53

Running time for iterative function: 9 Milli seconds

 Mean using Recursive function is: 4908.97

Variation using Recursive function is: 8.77065e+006

Standard deviation using Recursive function is: 2961.53

Running time for Recursive function: 6 Milli seconds

 For n=1500:

Mean using Iterative function is: 4531.62

Variance using Iterative function is: 8.7867e+006

Standard deviation using Iterative function is: 2964.24

Running time for iterative function: 7 Milli seconds

 Mean using Recursive function is: 4531.62

Variation using Recursive function is: 8.7867e+006

Standard deviation using Recursive function is: 2964.24

Running time for Recursive function: 7 Milli seconds

 For n=2000:

Mean using Iterative function is: 4641.43

Variance using Iterative function is: 8.57314e+006

Standard deviation using Iterative function is: 2927.99

Running time for iterative function: 7 Milli Seconds

 Mean using Recursive function is: 4641.43

Variation using Recursive function is: 8.57314e+006

Standard deviation using Recursive function is: 2927.99

Running time for Recursive function: 7 Milli Seconds