Why does the processor take the same amount of time to execute these two for loops (coded in Java)?

Question

public class FactorFinder{
  public static void main(String[] args) {      
    long n = ((long)Integer.MAX_VALUE+1)*2;
    boolean isPrime=true;

    for(long i=2;i<=n/2;i++){
        if(n%i==0){
            System.out.println(i + " is a factor of " + n);
            isPrime = false;
        }   
    }    
    if(isPrime == true) System.out.println(n+ " is a prime number");   
  }     
}

I wrote the above code to find the factors n, or if it didn't have any factors print "n is a prime" number. I temporarily set n=2^32 right there in the code to see how much time it would take for the program to completely run. It took 1 min 17 secs.

Then I changed the for loop as

for(long i=2;i<n;i++){

and expected it would take twice as much time for the program to complete. As you would expect, now that you have read my question, it only took 1 min 17 secs.

Am I right in thinking that the processor is somehow able to know that after n is greater than 2^32 / 2, it doesn't have to run the loop anymore, or even if it did, it doesn't have to check the condition of the if statement anymore?

I have an Intel core i3, JDK 1.7.0 running on Windows 7.

score 1 · Answer 1 · answered Nov 18 '12 at 07:11

1

It took half as long for the n/2 version on my machine. There's no way the compiler is smart enough to have figured out the kind of optimization you're thinking about.

Did you remember to save the source file and recompile before testing the second time? Forgetting that would explain the results you got, and I can't think of anything else that would.

answered Nov 18 '12 at 07:11

Michael Shaw

215
1
6

That's what I thought at first too. But I did save and compile. I even changed the IDE. Please tell me what kind of processor you have? – PrashanD Nov 18 '12 at 08:17
It can't be the processor. If it was an optimization, it would have to be the Java compiler. – David Schwartz Nov 18 '12 at 08:28
I thought it could be the processor because of branch predicting. See here, http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array and here http://en.wikipedia.org/wiki/Branch_predictor Simply put, branch predicting is when the processor can "get used to" making a decision when it's been making that same decision for a long time, so the processor, instead of doing a calculation to make the decision, takes a guess. – PrashanD Nov 18 '12 at 08:32
1

No branch predictor would be smart enough to reason about what the program will be doing in the future and realize that something the code tells it to calculate will be unnecessary for complex mathematical reasons. It's possible a compiler would do an optimization like that. I tried again with jdk 1.7 (I had been using 1.6) and got the same results. Some IDEs have their own compilers, so maybe try to compile & run it from the command line instead. – Michael Shaw Nov 18 '12 at 21:25
@Micael Shaw Well, I thought the branch predictor doesn't have to realize that what my "code tells it to calculate will be unnecessary" and it doesn't have to know mathematical reasons involved here. All it has to do is LOOK AT THE HISTORY of calculations made after i>n/2 and it can guess perfectly well that the condition for the next value of i would be false. That's what the branch predictor does, it looks at the history of decision making and makes a 90% accurate guess in general situations. In my code the accuracy would be 100%, wouldn't it? – PrashanD Nov 19 '12 at 16:08
@Prashan: If it did that, then it would decide to stop checking whether i was a factor after about 8, and it would run almost instantly, and tell you that the only factors of 2^32 are 1, 2, 4, and 8. It would be very, very fast, but it would be wrong. The branch predictor can tell that it's in the middle of a loop and tell the pipeline to fill itself with instructions that assume it will stay in the loop, but it can never say "don't bother calculating this" because it has no way of knowing whether or not the right answer will be the probable answer. – Michael Shaw Nov 19 '12 at 23:59

score 0 · Answer 2 · answered Mar 08 '13 at 08:08

0

It's pretty clever if compiler doesn't attempt to execute unnecessary calculations, cause it's not necessary to check if n is dividable by i, if i > root(n)

answered Mar 08 '13 at 08:08

Adrian Adamczyk

3,000
5
25
41

Why does the processor take the same amount of time to execute these two for loops (coded in Java)?

2 Answers2