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