## if and while

Write here if you have problems with your C source code

Moderator: Board moderators

### if and while

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?
Joseph Kurniawan
Experienced poster

Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

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..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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 /= i3.   i -= 2;4. i += 2;5. goto 1`

while:
Code: Select all
`1. if (num % i == 0)2.   num /= i3.   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.

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

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..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### time wasted

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) {
...
It seems to be impossible to find out everything, because new information appears faster than you can learn it... - this is the problem of our century.
quinn
New poster

Posts: 1
Joined: Wed Jun 02, 2004 6:27 pm
Location: Russia, Saratov

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.
Quantris
Learning poster

Posts: 75
Joined: Sat Dec 27, 2003 4:49 am