This article will describe how to build a more complex javascript application. I chose to build a number cruncher for finding sociable numbers. There are many idle browser out there and the new Worker-thread object (available in modern browsers) offers the complete power of all cpu cores. In the first part I will describe how to inherit javascript objects with the optimization steps and discuss the usage of a profiler. The second part will improve the performance with using Web Worker in threads for greater computing power and how to handle it.

introduction

Did you heard of perfect numbers? No? A number is perfect if the number is equal to the sum all proper positive divisors. The old greek mathematics found the following examples (or try out the demo):

The 6 has as positive divisors 1, 2 and 3 and the sum is 6.
The next perfect number is 28 with 1, 2, 4, 7 and 14
The 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
The 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064.

Funny but not easy to find more … Amicable numbers were known to the Pythagoreans and are two different numbers so related that the sum of the proper divisors of one of the numbers is equal to the other. For example, the smallest pair of amicable numbers is (220, 284); for the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71, and 142, of which the sum is 220.

If the cycle to reach the starting number (with the recursion of the sum of positive divisors) and the length of the cycles is greater than 2 they called sociable or multiperfect numbers”. Its a more general concept for the first two special cases.

If you are interested in the mathemical background there are many resources in the net:

• The Perfect Number Journey
• a little history about perfect numbers
• great source of Multiply Perfect Numbers from Achim Flammenkamp
• the book Unsolved Problems in Number Theory by Richard Guy
• Algorithms in the Study of Multiperfect and Odd Perfect Numbers by Sorli, Ronald

the motivation

Because no general formula exists to find all sociable numbers it would be nice to find a new cycle at first. There is some formula to find perfect numbers based on prime numbers but I will build only a number cruncher with testing a given range for perfect numbers. There are many other distributed computer projects (like the Great Internet Mersenne Prime Search) why not this part of number theory? But don’t think this is an easy task. After the first 200 years all mathematicians found only a few cycles. With the modern computing power all cycles under 100.000.000 were found – see the complete list at http://djm.cc/sociable.txt.

And I want to solve this in your browser – with javascript.

implementation

the algorithm

The com.unitedCoders.Numbers1 object realized the algorithm straight forward:

var com = com||{};
com.unitedCoders = com.unitedCoders||{};

com.unitedCoders.Numbers1 = function(){
    this.maxLoop = 100;
    /* calculate all divisors of n and return the sum of it
    @var n int  - number to be checked
    @return the sum of all divisors
    */
    this.calcSumOfDivisors = function(n) {
      //include the divisor 1
      var sum = 1;
      var middle = Math.sqrt(n);
      for (var i=2; i <= middle; i++) {
        if (n % i === 0) {
        sum += i;
        sum += n/i;
        }
      }
      return sum;
    };

The calcSumOfDivisors function finds the integer divisors with the modulo operator. The loop runs only up the square of the number because you can get directly the other of the divisor pair. For example if you found 3 is a divisor of 30 so is 30/3=10 a divisor too.

    /* generate a cycle and break if maxLoop reached or n=1 or n is too great
    @var start int - start number of loop
    @return [int] - calculated loop
    */
    this.calcCycle = function(start) {
      var last = start, f = [], max = 100*start, length;
        do {
            last = this.calcSumOfDivisors(last);
        length = f.push(last);
      } while (start!==last && last>1 && length<this.maxLoop && last<max);
      return f;
    };

To find a cylce of the sum of all divisors you can start recursively until getting the starting number. I chose a simple while-do loop ending with the starting number or break after 100 tries. If the found cycle ends with length of 1 it is a perfect number, with 2 a pair of amicable numbers are found and if the cycles end with more the 2 numbers the result could be sociable numbers. The largest known cycle at this time is 28. To limit the loop I will be pessimistic and try up 100 runs until my function gives up.

    /* Calculate the cycle, check if there is a loop and if n the first element,
       return the numbers as a list.
    @var n int - start number for checking
    @return [int] if n is starting point of a social number group
    */
    this.getMinSociable = function(n) {
        var f = this.calcCycle(n, this.maxLoop);
        // Check if it has a cycle
    if (n === f[f.length-1]) {
        //Check if n is the lowest member of the cycle
        var sorted = f.slice();
        sorted.sort(function(a,b){return a-b;});
            if (n === sorted[0]) {
                //correct the list, put the starting number at pos:0
                f.unshift(f.pop());
                return f;
            }
        }
        return;
    };
    /* Find sociable numbers from start to end
    @var start int - Starting number for checking
    @var end int - ending point for checking
    @return [ [int], ] list of sociable groups
    */
    this.findSociable = function(start, end) {
        var results = [];
        for (var i=start; i<end; i++) {
            var match = this.getMinSociable(i);
            if (match) {
                results.push(match);
            }
        }
        return results;
    };
};

The function getMinSociable() check if the result of calcCycle are sociable numbers and if is starts with the lowest number to get only one result. The seconds condition will prevent to find a cycle more the once.

first optimization step

If you running the functions in firefox with firebug you can profile all the function calls (since firebug 1.4.x the function count could be incorrect but the tendency is ok). Open the firebug console and start a search between 1 and 15.000. I got these function call list with executing times.

This is the result in firefox 3.5 in my tiny eeeBox with the typical netbook processor (Intel Atom n270 mobile processor with 1.6 MHz – to compare the times).

firefox 3.5, profiler output with my intel atom cpu (wrong counting of the function calls)

firefox 3.5, profiler output with my office intel p4 cpu

The run for 15.000 cycles takes 5.4 sec (3,4 sec on my P4 cpu) – most time in the deepest function calcSumOfDivisors. You notice that for checking 15000 numbers the calcSumOfDivisors-function will be called over 175.000 times. Many cycles end will 1 and a simple caching for the calculation would decrease the calls and speed up.

Caching before calculation

If a cache call is faster than a calculation it could be a good way for better performance. If the cache hit rate can save some calculation time do caching! In the example would a simple JavaScript object help to decrease the calcSumOfDivisors-function. The calcCycle-function will call the caching facade.

com.unitedCoders.numbers.getSumOfDivisors : function(n) {
    var sum = this.sumCache[n];
    if (sum) { return sum; }
    
    sum = this.calcSumOfDivisors(n);
    this.sumCache[n] = sum;
    return sum;
};

firefox 3.5, profiler output with my intel atom cpu

firefox 3.5, profiler output with my office intel p4 cpu

The overall time is only 4 sec (0.9 sec on my P4 cpu) and the number of calcCumOfDivisor decreased below to 20.000! I added a direct cache look-up in the calcCycle function to decrease the function calls so the getSumOfDivisor is only for “cache miss and saving the result” used.

no function calls

The result of the third step looks ugly. Because JavaScript runs in a interpreter eliminating all function calls could increase the calculator speed, but your code will become unreadable. This is only a try to test if it works.

This should save the time to calling the functions and initializing the local varibale scope. An other aspect is giving the JavaScript runtime optimizer a large block to work with it.

com.unitedCoders.Numbers3 = function(){
    this.findSociable = function(start, end) {
        var maxLoop = 100;
        var results = [];
        for (var n=start; n<end; n++) {
            //calcCycle
            var lastN = n, f = [], maxN = 100*n, length;
            do {
                //getSumOfDivisors
                if (!this.sumCache[lastN]) {
                    this.sumCache[lastN] = this.calcSumOfDivisors(lastN);
                }
                lastN = this.sumCache[lastN];
                length = f.push(lastN);
            } while (n!==lastN && lastN>1 && length<this.maxLoop && lastN<maxN);

            //getMinSociable
            if (n===lastN) {
                var sorted = f.slice();
                sorted.sort(function(a,b){return a-b;})
                if (n === sorted[0]){
                    f.unshift(f.pop());
                    results.push(f);
                }
            }
        }
        return results;
    };
};
com.unitedCoders.Numbers3.prototype = new com.unitedCoders.Numbers2();

firefox 3.5, profiler output with my intel atom cpu

firefox 3.5, profiler output with my office intel p4 cpu

Result: Wow – the firefox 3.5 runtime optimizer can work well with the one function version! The older firefox 3.0 show no benefit in this version – see the benchmark in the next section.

Use Webworker

Webworker is a new HTML5 feature supported by modern browsers since mozilla firefox 3.1, apple webkit or google chrome. It does not work on opera, firefox 3.0 or konqueror. The worker is a JavaScript object in a extra thread who can communicate with the main application via the function postMessage.

For the simple example I created a a “worker hook function” in my numbers.js file and started the cruncher object synchronous like in the normal version. The final version can split the number range in parts for each worker thread.

   worker = new Worker("numbers.js");
   worker.onmessage = function(resultStr) { window.alert(resultStr); }
   worker.postMessage("3,1,15000");

The Worker object is loaded, will start in background the calculation and give the result as json-string to the callback function (which shows as ugly alert box).

//this will load the local json2-file from crockford, got from http://json.org/
importScripts("json2.js");
//this is the called function from worker.postMessage
//@param {String} "variant,from,to"
onmessage = function(params) {
    var p = params.data.split(",");
    var worker = new com.unitedCoders['Numbers'+p[0]]();
    var results = worker.findSociable(+p[1], +p[2]);
    //this is the calling function for worker.onmessage
    postMessage(JSON.stringify(results));
};

I expect better results with using more than one worker. Best would be one worker per cpu core. Chrome scales perfectly because the browser has an extra worker process for every tab! Firefox has one process but I can see more the one working thread in top.

Get modern browser running in ubuntu

If you using ubuntu (or other apt-based linux) and don’t have the newest firefox (or didn’t upgrad to ubuntu 10.x), here is the command to get it directly. Firefox can be installed via

 > sudo apt-get install firefox-3.5

.

Because googles browser chrome is calling home, use the privacy cleaned version Iron chrome from SRWare (see Review here and here).

Or get the normal version via apt-get following the steps from ubuntugeek.com.

The other two big player apple safari and internet explorer won’t run natively under ubuntu. I will try to install safari with wine hoping the core JavaScript speed doesn’t differ. And for the internet explorer there is the fine ie4linux project.

Benchmarking the variants

How to benchmark the code? I created the three evolutionary code versions and three work modes. First the directly variant as normal JavaScript function, second run the same function in a Webworker in a thread. The third version will split the calculation in 4 parts and start 4 webworker to hit the score.

For testing the variants in different browser I choosed on my ubuntu eeeBox the following browser, because all candidates use different javascript engines:

results

My optimization in three variants works on every browser and result caching is OK. V8 will optimize my single function variant dramatically – the run-time JavaScript optimizer works great! The starting and communication overhead for the worker is reasonable and it can benefits while computing more the one second per thread.

The four thread worker version was not faster than the normal version? OK, with only one core on one cpu (my intel Atom) could threaded number crunching not scale! Testing on a four core CPU: Yes it works fine but not linear, try it out in the interactive demo (open the firebug console for logging info)!

But don’t forget your old-stuffed visitors (or internet explorer users): If your JavaScript calculations runs in chrome fine – your visitors with older browser will be frustrated! Factor 10 in calculation time is possible.

• Bio
• Latest Posts

Christian Harms

I am working as a software developer and project manager in germany. After my graduate computer science I started in 2000 as a developer for a warehouse management system. my python knowledge grow up as a team member for one of the TOP3 german portal and freemail services. 2012 switched to the automotive industry to share my knowledge about open source and agile development. In spare time I submit to some coding contests and interesed in smaller developments.

Latest posts by Christian Harms (see all)

• google code jam 2013 – tic-tac-toe-Tomek solution - April 16, 2013
• Google code jam 2013 – the lawnmower - April 14, 2013
• code puzzles and permutations - April 11, 2013