Timing functions

[giraffe1234]

I need to time the amount of time it takes to run a recursive function vs. an iterative function. Everytime I run the program I get 0. Is there a way to calculate in miliseconds vs. just seconds? Here is some of my code so you know what I'm doing

[MiiNiPaa]

1) Never include output in your measuring function. It is really slow. By outputting values you calculate you can slow down your calculation up to 100 times. It is unpredictable either, so any output you make will greatly increase measurement error.

2) Timer precision is low (on Windows CLOCKS_PER_SEC is usually 1000) and modern computers are really fast. Do at least 100 000 calculation (or more. you want at least 1 second of calculations) between measurements to make any sensible results.

[giraffe1234]

So how would I do that? Would I use a for loop like the following?

;
[/code]

[MiiNiPaa]

Yes, and check perfomence for both large and small numbers (recursive will be way slower on high numbers). Then compare them. It will be something like:

const unsigned repeats = 100000;
start_rec = clock();
for(int i=0; i<repeats ; i++) {
   fibonacci_rec(i % 100);
}
double low_rec_time = double(clock() - start_rec) / CLOCK_PER_SEC;
//low_rec_time /= repeats; //To get average time of one calcualtion 

start_rec = clock();
for(int i=0; i<repeats ; i++) {
   fibonacci_rec(1000 + i % 100);
}
double high_rec_time = double(clock() - start_rec) / CLOCK_PER_SEC;


start_rec = clock();
for(int i=0; i<repeats ; i++) {
   fibonacci_iter(i % 100);
}
double low_iter_time = double(clock() - start_rec) / CLOCK_PER_SEC;

start_rec = clock();
for(int i=0; i<repeats ; i++) {
   fibonacci_iter(1000 + i % 100);
}
double high_iter_time = double(clock() - start_rec) / CLOCK_PER_SEC;

[giraffe1234]

Is there anyway to print out the value of the fibonacci number before you print out the time it took to get there?

[MiiNiPaa]

Run loop measuring time, Then run anoter loop to output numbers.
Or store them in container when you loop and then output it.

[giraffe1234]

Okay thank you! Also when I just do the iterative I get results like .02 and .35 but when running recursively, nothing even comes up. Does it really just take that much longer? Or am I doing something wrong? This is how I wrote the code

//run recursive function for small number
     //call time 

Sorry for all the questions, but thank you so much for your help!

[MiiNiPaa]

Yes, naive recursive algorihm has complexivity of O(2ⁿ). That is really large number. I suggest you to use (i%10 + 1) or slightly larger in your small numbers loop, and do not try to do large numbers loop. I forgot about terrible perfomance of naive recursive function.