Tag Archives: timing

Timing ‘Prime time’

Follow me

Vinay Singh

Computer Teacher at Saint John's Academy
I am a GNU/Linux enthusiast and a computer science teacher by profession based at Allahabad, India. My hobbies include reading (mostly computer related stuff) and photography.
Follow me

Latest posts by Vinay Singh (see all)

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:

n isPrime1 isPrime2 isPrime3
1 2960 3058 2777
5 1108 940 49163
10 1267 786 740
50 1929 720 731
100 2946 770 735
200 4285 781 715
500 11291 764 786
1001 21007 1050 1455
5001 128459 865 1165
10001 1495611 2144 2540
50001 317681 1002 1613
60001 360096 1266 1651
70001 391876 1581356 4552
80001 346825 14924 1318
90001 407214 272037 4576
100001 460347 1169 2933

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.