C++

Forum

 
What is being asked to be completed?

mattho (16)
What is being asked to be completed? Is it just changing Maxn and running the program a few times?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
 PURPOSE.
To investigate enhancements to the GetTickCount() function for determining execution time
of a sequence of C++ code. In specific, it is probably better to make more than one measurement of execution time and to present some statistics regarding variation.


Procedure
Your task is to adapt the three- file example (FiboImp.h, FiboImp.cpp, TestingFibo.cpp)
of Lecture 11 to a three file solution (FiboImp.h, FiboImp.cpp, Prog07.cpp) which finds
the maximum and minimum execution times of the Fibonacci number computation
routines for six separate, unique runs at each value of n. An example of the desired
output of your solution is shown on the second page of this procedure. NOTE: do not
use the tail recursion implementation.

You might find it interesting to observe the measured execution time when your system
is \quiet" versus \noisy and busy" (that is, when youre running lots of applications
and interacting with them, web downloads and media use are good examples of busy).
Do not use very large values of n. Do have reasonable length execution
times for your hardware (1 second is not reasonable).


The
// idea is to look at the maximum and minimum execution
// times. Should see some variation, at least in the
// recursive version of the test.
buckner ~.../programs/prog07/solution> Prog07
Execution time for Fibonacci no. implementations
(ms min
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
n Recursive Iterative
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0 0 ( 0 --- 0) 0 ( 0 --- 0)
1 1 ( 0 --- 0) 1 ( 0 --- 0)
2 1 ( 0 --- 0) 1 ( 0 --- 0)
3 2 ( 0 --- 0) 2 ( 0 --- 0)
4 3 ( 0 --- 0) 3 ( 0 --- 0)
5 5 ( 0 --- 0) 5 ( 0 --- 0)
6 8 ( 0 --- 0) 8 ( 0 --- 0)
7 13 ( 0 --- 0) 13 ( 0 --- 0)
8 21 ( 0 --- 0) 21 ( 0 --- 0)
9 34 ( 0 --- 0) 34 ( 0 --- 0)
10 55 ( 0 --- 0) 55 ( 0 --- 0)
11 89 ( 0 --- 0) 89 ( 0 --- 0)
12 144 ( 0 --- 0) 144 ( 0 --- 0)
13 233 ( 0 --- 0) 233 ( 0 --- 0)
14 377 ( 0 --- 0) 377 ( 0 --- 0)
15 610 ( 0 --- 0) 610 ( 0 --- 0)
16 987 ( 0 --- 0) 987 ( 0 --- 0)
17 1597 ( 0 --- 0) 1597 ( 0 --- 0)
18 2584 ( 0 --- 0) 2584 ( 0 --- 0)
19 4181 ( 0 --- 0) 4181 ( 0 --- 0)
20 6765 ( 0 --- 0) 6765 ( 0 --- 0)
21 10946 ( 0 --- 0) 10946 ( 0 --- 0)
22 17711 ( 0 --- 0) 17711 ( 0 --- 0)
23 28657 ( 0 --- 16) 28657 ( 0 --- 0)
24 46368 ( 0 --- 0) 46368 ( 0 --- 0)
25 75025 ( 0 --- 0) 75025 ( 0 --- 0)
26 121393 ( 0 --- 15) 121393 ( 0 --- 0)
27 196418 ( 0 --- 0) 196418 ( 0 --- 0)
28 317811 ( 0 --- 16) 317811 ( 0 --- 0)
29 514229 ( 0 --- 16) 514229 ( 0 --- 0)
30 832040 ( 0 --- 16) 832040 ( 0 --- 0)
31 1346269 ( 15 --- 16) 1346269 ( 0 --- 0)
32 2178309 ( 15 --- 32) 2178309 ( 0 --- 0)
33 3524578 ( 31 --- 47) 3524578 ( 0 --- 0)
34 5702887 ( 47 --- 63) 5702887 ( 0 --- 0)
35 9227465 ( 93 --- 125) 9227465 ( 0 --- 0)
36 14930352 ( 156 --- 172) 14930352 ( 0 --- 0)
37 24157817 ( 234 --- 297) 24157817 ( 0 --- 0)
38 39088169 ( 391 --- 453) 39088169 ( 0 --- 0)
39 63245986 ( 641 --- 718) 63245986 ( 0 --- 0)
40 102334155 ( 1063 --- 1094) 102334155 ( 0 --- 0)
41 165580141 ( 1718 --- 1782) 165580141 ( 0 --- 0)
42 267914296 ( 2750 --- 2890) 267914296 ( 0 --- 0)
43 433494437 ( 4485 --- 4719) 433494437 ( 0 --- 0)
44 701408733 ( 7250 --- 7640) 701408733 ( 0 --- 0)
45 1134903170 (11969 --- 12172) 1134903170 ( 0 --- 0)


FIBOIMP.h
1
2
3
4
5
6
7
8
9
10
11
12
 
// FiboImps.h
// Declarations for Fibonacci implementations.

#ifndef FIBOIMPS_H
#define FIBOIMPS_H

unsigned long int FiboRecursive(int);

unsigned long int FiboIterative(int);

#endif


Fiboimp.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
  // FiboImps.cpp
// Definitions of the Fibonacci implementations.

unsigned long int FiboRecursive(int n)
{
  if (n <= 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  } else {
  
    return FiboRecursive(n-2)+FiboRecursive(n-1);
  }
}

unsigned long int FiboIterative(int n)
{
  long int result=1;
  long int previous=-1;

  for (int i=0; i<=n; i++) {
    long int sum = result+previous;
    previous = result;
    result = sum;
  }

  return result;
}


TestingFibo.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
  // TestingFibo.cpp
// Demonstration of the use of a Windows API function for
// getting a rough measurement comparison on execution time
// of a recursive and an iterative computation of Fibonacci.

#include <iostream>
using std::cout;
using std::endl;

#include <iomanip>
using std::setfill;
using std::setw;

#include "FiboImp.h"

#include <windows.h>

const int MAXN(45);

int main()
{
  unsigned long int before, after, diff, result;

  cout << "Execution time for Fibonacci no. implementions (ms)\n";
  cout << setfill('+') << setw(64) << "+" << endl << setfill(' ');
  cout << setw(4) << "n" << setw(30) << "Recursive"
    << setw(30) << "Iterative" << endl;
  cout << setfill('+') << setw(64) << "+" << endl << setfill(' ');
  for (int n=0; n<=MAXN; n++) {
    cout << setw(4) << n;
      before=GetTickCount();
        result=FiboRecursive(n);
      after=GetTickCount();
      diff=after-before;
    cout << setw(20) << result << setw(10) << diff;
      before=GetTickCount();
        result=FiboIterative(n);
      after=GetTickCount();
      diff=after-before;
    cout << setw(20) << result << setw(10) << diff;
    cout << endl;
  }

  return 0;
}
Topic archived. No new replies allowed.