I am trying to compare the speed of functions in C, and there is something that I cannot understand,
I tried to get the sum of primes (from 1 to 100000)
in recursive I get 2.1 .... sec
int sumOfPrime(unsigned int top) { if( top % 2 == 0 ) top -= 1; static int total = 2; // sum of prime numbers int i; int control=0; // prime or not if( top == 2 | top < 2) return total; for (i = 3; i < (top/2)+1; i++) { if( top % i == 0 ) // if there is a multiple { control++; break; } } if( control == 0 ){ total += top; } return sumOfPrime(top-2); }
in an iterative state that is O (n ^ 2), I get 1.14 s
int sumOfPrime(unsigned int top) { unsigned int total = 2; int count; int i,j; for (i = 3; i < top; i+=2) { count = 0; for (j = 3; j < (i/2)+1; j+=2) { if( i % j == 0 ) { count++; break; } } if( count == 0 ){ total += i; } } return total; }
and then I tried it in the tail recursive, and yet I got 2.1 almost exactly at the same time,
int sumOfPrime(unsigned int top,unsigned int total) { if( top % 2 == 0 ) top -= 1; //static int total = 2; int i; // for for loop int control=0; // prime or not if( top == 2 | top < 2) return total+2; for (i = 3; i < (top/2)+1; i++) { if( top % i == 0 ) // if there is a multiple { control++; // add +1 to control break; } } if( control == 0 ){ // if its primme total += top; } return sumOfPrime(top-2,total); }
Here we use recursive for speed in some situations, such as merge-sort, so what are situations?
Are there any special rules on when to use it for speed? or what am I missing? I am really more convenient recursive than iterative, and I really want to use it, but this difference in speed gives me stomach pain.
source share