In my last post I discussed three methods for primality test suitable for ICSE/ISC students. The first method was quite slow, the second and third methods were considerably faster. In this post we will see how we can measure or visualize the performance of an algorithm. We can use profiling tools which comes bundled with major IDEs like Eclipse or Netbeans, unfortunately BlueJ, the recommended editor by CISCE doesn’t come with a inbuilt profiler.  Instead of downloading and learning a new tool we will see how to time a method in Java. The timing methods in java which we will employing in this post are not very accurate and depending on the hardware and the platform used but since we are interested in overall trends this inaccuracy won’t be an issue.

Java has a function System.nanoTime() which returns the current value of the running Java Virtual Machine’s high-resolution time source, in nanoseconds. We can use System.nanoTime() to measure the time elapsed in executing a certain code e.g.

long startTime = System.nanoTime();
// ... the code being measured ...
long estimatedTime = System.nanoTime() - startTime;

The above will return the time elapsed in nano seconds. Students are advised to visit the documentation of System.nanoTime() for details.

In order to apply the above logic in the isPrime( ) implementation of the previous post we will rename the three isPrime() implementation to isPrime1(), isPrime2 and isPrime3() respectively. We will also add some code to call and time the above functions. The final code will be as follows:

class Prime{
    public static boolean isPrime1(int number){
        for(int i=1; i<=number; i++){
            if(number%i==0){
                factorCount++;
            }
        }
        if(factorCount==2) return true;
        else return false;
    }

    public static boolean isPrime2(int number){
        if(number<2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            for(int i=3; i<number;i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isPrime3(int number){
        if(number<2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            int limit = (int)Math.sqrt(number);
            for(int i=3; i<=limit;i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }

    public static void benchmark(){
        long startTime,estimatedTime;
        boolean primeStatus=false;
        int testcase[]={1,5,10,50,100,200,500,1000,5000, 10000, 50000, 60000,70000,80000,90000, 100000};
        System.out.println("n\tisPrime1\tisPrime2\tisPrime3");
        for(int i=0; i<testcase.length; i++){
            System.out.print(testcase[i]+"\t");

            startTime= System.nanoTime();
            primeStatus=isPrime1(testcase[i]);
            estimatedTime = System.nanoTime()- startTime;
            System.out.print(estimatedTime+"\t\t");

            startTime= System.nanoTime();
            primeStatus=isPrime2(testcase[i]);
            estimatedTime = System.nanoTime()- startTime;
            System.out.print(estimatedTime+"\t\t");

            startTime= System.nanoTime();
            primeStatus=isPrime3(testcase[i]);
            estimatedTime = System.nanoTime()- startTime;
            System.out.println(estimatedTime);

        }

    }

    public static void main(String args[]){
        benchmark();
    }
}

When the above code is executed the output will vary due to differences in hardware and software. On my system the output is as follows:

All time intervals are in nano seconds. The difference between the runtime of isPrime1() and isPrime2() is clearly evident but one may be surprised that isPrime3() is not the best for all the given set of values! The reason for this discrepancy is that the Math.sqrt() function of Java returns a double value and is computationally intensive. The problem can be removed by using a custom function for computing the square root which optimized for integers. I am not going to discuss them over here because they lie outside the scope of ICSE/ISC syllabus, those interested can visit http://atoms.alife.co.uk/sqrt/ for one such implementation.