Name: Tom Hall on 'The Genuine Sieve of Eratosthenes'
Start: 2015-09-16T18:30:00+01:00
End: 2015-09-16T21:30:00+01:00
Location: Skills Matter at CodeNode

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)

Tom Hall

Philip Potter

Papers We Love - London

Technology

Computer Science

Computer Programming

Academics

Computational Science and Engineering

Scientific Computing

Tom Hall on 'The Genuine Sieve of Eratosthenes'

Skills Matter at CodeNode

Share

Papers We Love - London

Tom Hall on 'The Genuine Sieve of Eratosthenes'

Papers We Love - London

Details

Members are also interested in