JavaScript Rules

Finding prime numbers with Javascript

A few days ago I introduced a friend of mine Jorge Rocha to SPOJ an online judge system for user-submitted programs, one of the first problems that he tried was the Prime Generator it consisted in finding all primes in a given range of numbers, after some time and few different algorithms he asked me if I had any tips to help him, although he had the correct algorithm (Sieve of Eratosthenes) something was clearly missing, the solution wasn’t fast enough and I had no clue where to go from there, so as usual when a question like that comes up I resort to Mauro Persano… and obviously he knew the answer, he taught us how to apply a heuristic to the algorithm to help solve the problem and after doing so the code worked and the solution was approved.

Although I’m not really into crazy algorithms challenges I thought I’d give it a try just to see how fast the solution would be in JS, note that most of the solutions submitted are in C/C++ or Java, much faster than JS and to make things worst the interpreter was Rhino, anyways we went ahead and recreated the solution in Javascript, so now it was time to test it… a little more tweaking to make it receive inputs via console and we had it running, right away we realized that our output via stdout was slowing us down, printing 10 times in a row all primes until 1 billion in the shell is not really fast but it was required to, I knew we had little or no chances to get approved but anyways we tried… and as I suspected we didn’t get approved :(, but I decided to test locally in different browsers/engines with and without output.

Here are the results, I also built a test runner so you can test on your own:

  • Chrome is usually the best, is blazing fast but it chokes when outputting the results through WebKit
  • Rhino does a great job specially with a high number of runs because of JVM
  • Firefox runs nicely with short ranges but stops the script because of the long time running
  • Opera wasn’t fast but it never crashed or stopped
Browser/Engine # of runs Avg(ms) 0 - 100 thousand Avg(ms) 0 - 1 million
Rhino 1.7 * 10 250 2330
Firefox 3.5.3 * 10 670 Stopped
Chrome 4.0 * 10 32 3050
Opera 10 * 10 540 4956
Rhino 1.7 100 34 304
Firefox 3.5.3 100 20 Stopped
Chrome 4.0 100 9 128
Opera 10 100 100 1213

* With output (tested under Ubuntu 9.04 Jaunty)

Disclaimer: Any viewpoints and opinions expressed herein are those of the authors and do not, in any way, reflect those of Twitter, Yahoo! or anyone else.