if and while

[Joseph Kurniawan]

Consider this code
[c]
for(i=3;i<=sqrt(j);i+=2){
if(num%i==0){num/=i;printf("%i ",i);i-=2;}
}
[/c]
with this one:
[c]
for(i=3;i<=sqrt(j);i+=2){
while(num%i==0){num/=i;printf("%i ",i);}
}
[/c]

Those two are the part of my 583 - Prime Factor code.
With the first code AC in 4,......
But with the second, AC in 9,7........... (That's too close, baby)
Anybody know what could've caused this?

[Larry]

Loops do have an initialization cost, though I didn't realize it was THAT high...

You can do more optimizations though, like replacing

Code: Select all

i <= sqrt( j )


with

Code: Select all

i * i <= j


Since sqrt is more expensive..

[UFP2161]

Are you sure that's the problem code?

I would think the 'if' would take a tad bit longer, because if you think about how it *should* be executing the code:
if:

Code: Select all

1. if (num % i == 0)
2.   num /= i
3.   i -= 2;
4. i += 2;
5. goto 1

while:

Code: Select all

1. if (num % i == 0)
2.   num /= i
3.   goto 1

After running the two differing codes on my machine (looping it 2500 times over the same 'j' and 'num'), I got 6.509s for 'while' and 6.489s for 'if' (which does prove my above theory wrong), but the times aren't even more than a tenth of a second off.

[Larry]

One possible reason could also be that the while loop puts the program size just a tad over the limit for lower level cache, thus making it more expensive, since you also have to factor in the memory transfers...

but shouldn't happen for such small program sizes.. so I don't know.. maybe when I get home, I'll compile it into asm and check it out.. or someone could do it..

[quinn]

I believe that execution time increases in the second case due to that sqrt(j) is evaluated more often:
- in the first case it is evaluated only when i is increased actually;
- in the second case it is evaluated every time one of the following happens: (1) i is increased actually, or (2) num is divided by i.

Remember, that conditional expression is evaluated completely every loop iteration.

You can avoid this effect of time waste by replacing sqrt(j) with a precalculated, i.e.:

sqrt_j=sqrt(j);
for (i3; i<=sqrt_j; i+=2) {
...

[Quantris]

but isn't sqrt(j) evaluated more often with the if construct, since there is only one num division per iteration of the for loop, but with the while loop it only loops through the for loop once for each i...

anyway, you should definitely store sqrt(j) since it is constant.