By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,574 Members | 1,205 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,574 IT Pros & Developers. It's quick & easy.

measuring execution time for C++ program

P: 6
Hi,
I want to calculate execution time for a program computing fibonacci number in C++. I have programmed two functions (one using recursion and other using divide and conquer huristic) to compute fibonnaci number for (n=4,8,16,32,64). Now i want to compare these two methods. Though i have used following method to compute execution time but it is not precise as yielding 0 ticker time for n=4,8,16 in both the cases

Expand|Select|Wrap|Line Numbers
  1. double execClock(clock_t c1,clock_t c2)
  2.         {
  3.             double t=clock1-clock2;
  4.             double tim=(t*10)/CLOCKS_PER_SEC;
  5.             return tim;
  6.         }
  7.  
Is there anyother method which is more accurate for lower values of n, i am working in Inet/Windows XP/Dev C++ environment?

While following using recursive method

Expand|Select|Wrap|Line Numbers
  1.     int fib(int n)
  2.          {
  3.             if (n <= 1)
  4.                return n;
  5.             else
  6.                return fib(n-1) + fib (n-2);
  7.          }
  8.  
i can not compute fibonacci number for n=64, just system gets hanged, CPU usage reaches to 97% for the application, it seems it has struk in the computation

With Regards
Jianyi
Sep 29 '07 #1
Share this Question
Share on Google+
6 Replies


Savage
Expert 100+
P: 1,764
Hi,
I want to calculate execution time for a program computing fibonacci number in C++. I have programmed two functions (one using recursion and other using divide and conquer huristic) to compute fibonnaci number for (n=4,8,16,32,64). Now i want to compare these two methods. Though i have used following method to compute execution time but it is not precise as yielding 0 ticker time for n=4,8,16 in both the cases

Expand|Select|Wrap|Line Numbers
  1. double execClock(clock_t c1,clock_t c2)
  2.         {
  3.             double t=clock1-clock2;
  4.             double tim=(t*10)/CLOCKS_PER_SEC;
  5.             return tim;
  6.         }
  7.  
Is there anyother method which is more accurate for lower values of n, i am working in Inet/Windows XP/Dev C++ environment?

While following using recursive method

Expand|Select|Wrap|Line Numbers
  1.     int fib(int n)
  2.          {
  3.             if (n <= 1)
  4.                return n;
  5.             else
  6.                return fib(n-1) + fib (n-2);
  7.          }
  8.  
i can not compute fibonacci number for n=64, just system gets hanged, CPU usage reaches to 97% for the application, it seems it has struk in the computation

With Regards
Jianyi
The most precise method i know is QueryPerformanceCounter and QueryPerformanceFrequency which are defined in windows.h.

You use it like:

Expand|Select|Wrap|Line Numbers
  1. LARGE_INTEGER lFreq;
  2. LARGE_INTEGER lTime1;
  3. LARGE_INTEGER lTime2;
  4. long diffTicks;
  5. float diffSecs;
  6.  
  7. QueryPerformanceCounter(&lFreq);
  8. QueryPerformanceFrequency(&lTime1);
  9. //function
  10. QueryPerformanceFrequency.(&lTime2);
  11. diffTicks=lTime1.QuadPart-lTime2.QuadPart;//ticks passed
  12. diifSecs=(diffTicks/lFreq.QuadPart);//secs passed.
Savage
Sep 29 '07 #2

P: 6
Thanks for reply

but it is producing no result; 0 ticks and 0 seconds for each n i.e. 4,8,16, 32

Expand|Select|Wrap|Line Numbers
  1.   while (quit != 'x')
  2.             {
  3.                 LARGE_INTEGER lFreq;
  4.                 LARGE_INTEGER lTime1;
  5.                 LARGE_INTEGER lTime2; 
  6.                 long diffTicks;
  7.                 float diffSecs;
  8.                 int i;
  9.                 for(i=4;i<=66;i=i*2)
  10.                   {
  11.                    QueryPerformanceCounter(&lFreq);
  12.                    QueryPerformanceFrequency(&lTime1);
  13.                    cout<<fib(i);
  14.                    QueryPerformanceFrequency(&lTime2);
  15.                    diffTicks=lTime1.QuadPart-lTime2.QuadPart;//ticks passed
  16.                    diffSecs=(diffTicks/lFreq.QuadPart);//secs passed.
  17.                    cout<<" With ticks: " <<diffTicks<<" and seconds: "<<diffSecs<<endl;
  18.                   }       
  19.                 cout << endl << " Press x to quit "<<endl;
  20.                 cin >> quit;
  21.             };
  22.  
  23. ===========================================
  24.  int fib(int n)
  25.          {
  26.             if (n <= 1)
  27.                return n;
  28.             else
  29.                return fib(n-1) + fib (n-2);
  30.          }
  31.  
Output is zero ticks and zero seconds for each computed number

Jianyi
Sep 29 '07 #3

Savage
Expert 100+
P: 1,764
My bad,wher you have QueryPerformanceFrequency put QueryPerformanceCounter and vise versa.Also subtract time2 from time 1 not vise versa.

Savage
Sep 29 '07 #4

P: 6
Though i have got time2 - time1 but notgetting about function calls. Do you mean this way

Expand|Select|Wrap|Line Numbers
  1.                    QueryPerformanceFrequency(&lTime1);
  2.                    QueryPerformanceCounter(&lFreq);
  3.                    cout<<fib(i);
  4.                    QueryPerformanceFrequency(&lTime2);
  5.                    diffTicks=lTime2.QuadPart-lTime1.QuadPart;//ticks passed
  6.                    diffSecs=(diffTicks/lFreq.QuadPart);//secs passed.
  7.  

Jianyi
Sep 30 '07 #5

Savage
Expert 100+
P: 1,764
Though i have got time2 - time1 but notgetting about function calls. Do you mean this way

Expand|Select|Wrap|Line Numbers
  1.                    QueryPerformanceFrequency(&lTime1);
  2.                    QueryPerformanceCounter(&lFreq);
  3.                    cout<<fib(i);
  4.                    QueryPerformanceFrequency(&lTime2);
  5.                    diffTicks=lTime2.QuadPart-lTime1.QuadPart;//ticks passed
  6.                    diffSecs=(diffTicks/lFreq.QuadPart);//secs passed.
  7.  

Jianyi
No,like this:
Expand|Select|Wrap|Line Numbers
  1. QueryPerformanceFrequency(&lFreq);
  2. QueryPerformanceCounter(&lTime1);
  3. //function
  4. QueryPerformanceCounter(&lTime2);
  5. .
  6. .
  7. .
  8. .
Sep 30 '07 #6

P: 6
Thank you

Now it is fine

Jianyi
Oct 1 '07 #7

Post your reply

Sign in to post your reply or Sign up for a free account.