Performance

I was using a prime number generator for some browser testing (very nice for heavy duty testing by the way, add a zero and see the browser crash), when I thought of some improvements I could make. I started out with this code which is quite standard. Variants of this one can be found all over the internet:

//Put all prime numbers until max in an array
function normalPrime(max){
    var primes = new Array();
    //Loop through all numbers
    for(var i = 1; i <= max; i++){
        var isPrime = true;
        for(var j = 2; j < i; j++){
            //If dividible by that number, stop, isn't a prime number
            if(i%j == 0){
                isPrime = false;
                break;
            }
    }
    //If it is, add it to the array
    if(isPrime) 
        primes.push(i);
    }
    return primes;
}

With this code I could get the prime numbers until 29'000 in 1 second (using google chrome). First I changed the divider loop a little so it only goes to half the number that's being tested. For example if we're testing 19, 17 won't be tested as the result can never be without a comma. This is what the code becomes:

//Put all prime numbers until max in an array
function betterPrime(max){
    primes = new Array();
    //Loop through all numbers
    for(var i = 1; i <= max; i++){
        var isPrime = true;
        //Put the half in a variable, so it doesn't need to be calculated at every iteration
        var half = i/2
        for(var j = 2; j <= half; j++){
            //If dividible by that number, stop, isn't a prime number
            if(i%j == 0){
                isPrime = false;
                break;
            }
    }
    //If it is, add it to the array
    if(isPrime) 
        primes.push(i);
    }
    return primes;
}

This gives a small improvement, as we can now get the prime numbers until 33'000 in 1 second. As you see, by adding one simple line, the code goes much faster. But it can be improved much more:

First of all, you only need to check if the number can be divided until it's square root. Why? Because the following mathematical statement is always true: if a/b=c then a/c=b. So if we find a number bigger than the the square root that can divide the searched number, we will already have found the smaller one. Let's take 20 as an example (square root = 4.47): 20/10 = 2, which means that 20/2=10, the fact that 20 is not a prime number has already been checked whith the number 2. So there's no need to continue looking once we're over a number's square root (I'm not going to do a mathematically correct demonstration here, so if you want one, there probably is one somewhere on the internet).

The second important speed gain is to avoid doing the same test several times. For example if you're testing a number, and it can't be divided by 5, it won't be divided by 15 (5x3) either. If you look a bit further you can see that you only need to test your number with the prime numbers you've already found.

And a third gain can be obtained by only testing uneven numbers and hardcoding 2 as a prime number. This gives us the following code:

//Put all prime numbers until max in an array
function intelligentPrime(max){
    primes = new Array();
    //Put in 2 as it won't be found by the loop
    primes.push(2);
    //Only check uneven numbers
    for(var i = 3; i <= max; i+=2){
        var isPrime = true;
        //Calculate the square root once instead of at each iteration
        var squareRoot = Math.sqrt(i);
        //Lookup the length once instead of at each iteration
        var curPrimeLength = primes.length;
        for(var j = 0; j < curPrimeLength; j++){
            var curNum = primes[j];
            //If the current number is bigger than the square root, stop
            if(curNum > squareRoot)
                break;
            //Check if it can be divided
            if(i%curNum == 0){
                isPrime = false;
                break;
            }
        } 
        //If it is, add it to the array
        if(isPrime) 
        primes.push(i);
    }
    //Add 1 at the beginning of the array later, as every number can be divided by it and would return 0 primes
    primes.unshift(1);
    return primes;
}

This code can now find all prime numbers until 1'000'000 in one second, with the same browser and the same computer, which is quite a massive improvement. The conclusion? You should think before you start writing your code, as the fastest solution (performance) isn't always the easiest one (coding). Second conclustion: just because the computer CAN calculate everything for you doesn't mean he should do all the work. Help him a little bit.

Comments

Add New

RSS

The Tricky.net

Web

3.23 Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved."