CODEWITHSUNDEEP
javaperformancetimefor-loopprocessor
PrashanD
PrashanD

Reputation: 2764

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

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.

Upvotes: 0

Views: 129

Answers (2)

Adrian Adamczyk
Adrian Adamczyk

Reputation: 3070

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)

Upvotes: 0

Michael Shaw
Michael Shaw

Reputation: 225

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.

Upvotes: 1

Related Questions