Home ›

Number crunching with javascript - a tutorial

Christian Harms's picture
by Christian Harms on Fri, 02/05/2010 - 01:01
in

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 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:

  1. var com = com||{};
  2. com.unitedCoders = com.unitedCoders||{};
  3.  
  4. com.unitedCoders.Numbers1 = function(){
  5.     this.maxLoop = 100;
  6.     /* calculate all divisors of n and return the sum of it
  7.     @var n int  - number to be checked
  8.     @return the sum of all divisors
  9.     */
  10.     this.calcSumOfDivisors = function(n) {
  11.       //include the divisor 1
  12.       var sum = 1;
  13.       var middle = Math.sqrt(n);
  14.       for (var i=2; i <= middle; i++) {
  15.         if (n % i === 0) {
  16.         sum += i;
  17.         sum += n/i;
  18.         }
  19.       }
  20.       return sum;
  21.     };

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.

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

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.

  1.     /* Calculate the cycle, check if there is a loop and if n the first element,
  2.        return the numbers as a list.
  3.     @var n int - start number for checking
  4.     @return [int] if n is starting point of a social number group
  5.     */
  6.     this.getMinSociable = function(n) {
  7.         var f = this.calcCycle(n, this.maxLoop);
  8.         // Check if it has a cycle
  9.     if (n === f[f.length-1]) {
  10.         //Check if n is the lowest member of the cycle
  11.         var sorted = f.slice();
  12.         sorted.sort(function(a,b){return a-b;});
  13.             if (n === sorted[0]) {
  14.                 //correct the list, put the starting number at pos:0
  15.                 f.unshift(f.pop());
  16.                 return f;
  17.             }
  18.         }
  19.         return;
  20.     };
  21.     /* Find sociable numbers from start to end
  22.     @var start int - Starting number for checking
  23.     @var end int - ending point for checking
  24.     @return [ [int], ] list of sociable groups
  25.     */
  26.     this.findSociable = function(start, end) {
  27.         var results = [];
  28.         for (var i=start; i<end; i++) {
  29.             var match = this.getMinSociable(i);
  30.             if (match) {
  31.                 results.push(match);
  32.             }
  33.         }
  34.         return results;
  35.     };
  36. };

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.

Fave added

from CodeFave on Mon, 02/08/2010 - 17:15

Your story was featured in CodeFave Here is the link to vote it up and promote it: http://www.codefave.com

Comments

Solutions for the google code jam 2012 qualify round | unite's picture
Pingback
Solutions for the google code jam 2012 qualify round | unite (not verified) - Sun, 04/15/2012 - 22:16

[...] The third exercise is a number crunching problem and looks like my perfect number search article. [...]