In preparation for some interviews (do you know of a great company in Portland, OR? Let me know!), I’ve been studying various algorithms and rebuilding my Big(O) notation musculature. The Sieve of Eratosthenes is a simple algorithm for calculating primes with O(n log n) complexity when implemented with regular loops.

In order to really familiarize myself with these algorithms, I thought it would be fun to implement them in AngularJS. Not only does AngularJS enable you to build testable JavaScript code, but the recent animation support made me think I could make the algorithms really lively in a way that other languages don’t easily facilitate. I like the result.

https://www.youtube.com/v/7jwDwXUnRpY

The algorithm is really simple: take a list of numbers and then let P equal 2. Iterating until you have gone past the end of the list, take P multiplied by 2,3,4,5, etc, and mark those numbers as composite numbers. Once you have marked the composites which are multiples of P in the list, look for the first number past P: this is a prime, and the next value of P. Then, repeat the process again and again until P is larger than the size of the list. All unmarked values are the prime numbers.

As I’ve been studying the various algorithms, I like to start with some tests to verify that my final code works. AngularJS makes writing testable JS code so easy. Here is my test:

Yeah, yeah, I know this is coffeescript and not JavaScript.

My test generates a list of numbers, then runs the algorithm. I check to see that 5 is prime, and that 8 is not prime. I verify that the first and second primes in the primes cache are 3 and 5, and that the last one is 97. I cheated by following along using this example. I use $timeout inside the implementation code to slow down the algorithm for human consumption, but in the tests I don’t need that, so I mocked out timeout so it just immediately runs the callback.

After some thought, it makes sense to have two algorithsm, one with the timeouts to delay execution for doing the animations, and anothe pure algorithm implemented strictly with loops. These two should produce the same results, so the tests are identical. You can see one of the algorithms is called SieveOfE and one is called SieveOfEwoT (“without the timeout”).

Once I had these tests, I could run karma test runnner against them, and run until my tests passed. You can find the karma config file in the gist which contains all the files (run it with the command karma start karma.js).

The code to do the sieve turned out to be surprisingly compact. I’m sure that is all CoffeeScript’s fault.

AngularJS handles most of the work here, rebuilding the DOM with the proper CSS once a new calculation has completed. I wanted to really make it pop, so to speak, so I added a CSS3 explosion animation. AngularJS makes this so easy: when you use ng-class any new classes added after a $digest cycle also include a special class with the -add postfix. I added an animation inside of .prime-add to make those primes pop out of the page when the prime was found. This only works on Chrome and other webkit browsers, because I am too lazy to add two other prefixes.

The challenges in writing this algorithm using JavaScript or AngularJS

• Indexing from 0 in JavaScript and then figuring out where to convert to a 1-based index was tiresome. I ended up generating my list including the number 0 and then hiding it in the HTML (hence the ng-if="0 != $index")
• The animation does not truly reflect the steps involved. I added timeouts at points which I thought were interesting, but a better way to do it might be to alias all the methods defined on the scope and wrap timeouts around them. This has its own set of problems, because wrapping in an asynchronous timeout is not the same as wrapping in a synchronous function. Ah, how I wish we had the new JS proxy support. You can see that towards the end it looks like the algorithm is accelerating, but in fact the computational time is not increasing at this point.
• The algorithm with timeouts uses recursion which means that using large arrays of numbers will definitely hit stack space limitations. Could this be tail-call optimized (not if it is JS, right)? And, the first algorithm is not O(n log n) as written.

To play with all this yourself, make sure you have ruby and nodejs installed; then clone the gist and then run these commands:

$ coffee -c e.coffee # compile to JS for running in the browser $ powder link # make sure you have the powder gem and pow.cx installed $ open http://9965127.dev/e.html