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