Past Meetup

Tom Hall on 'The Genuine Sieve of Eratosthenes'

This Meetup is past

23 people went

Location image of event venue

Details

The paper, by Melissa O’Neill, is available here (https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf).

I like it because I first read it not knowing Haskell very well and I read through the paper a few times and had a wonderful a-ha moment with a sentence or two that made the idea click and was able to implement it in Python. I have since re-done it in Clojure so you will see it done 3 ways (and hopeful I will share an a-ha moment with you)

"""A much beloved and widely used example showing the elegance and simplicity of lazy functional programming represents itself as "The Sieve of Eratosthenes." The paper shows that this example is not the sieve and presents an implementation that actually is."""

Starting with the classic one-liner sieve

sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]

primes = sieve [2..]

O'Neill proceeds to show why this standard rendition of the Sieve of Eratosthenes does not in fact "cross-off" the multiples of each prime in the same way the "real" Sieve does.

She notes that "Some readers may feel that despite all of these concerns, the earlier algorithm is somehow morally the Sieve of Eratosthenes. I would argue, however, that they are confusing a mathematical abstraction drawn from the Sieve of Eratosthenes with the actual algorithm. The algorithmic details, such as how you remove all the multiples of 17, matter."

As this is at Skills Matter please also sign up there (https://skillsmatter.com/meetups/7328-papers-we-love-september-meet-up)