I read this interesting paper, The Genuine Sieve of Eratosthenes (PDF) by Melissa O'Neill, when it was discussed on Lambda the Ultimate. I came back to look at it again today because I wanted to improve my Haskell fluency, which I only seem to exercise when I read papers like this. I decided to try to correctly construe the Haskell code in the paper by implementing the algorithms in Python. I focused on reproducing the laziness but not the functional style because I could substitute iterators for lazy lists but had to use conventional control structures for all the pattern matching and tail calls.

#!/usr/bin/env python

# Author: Jared Brothers

#

# A Python version of the Haskell code from

# "The Genuine Sieve of Eratosthenes"

# www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

#

import heapq, itertools, operator

def sieve(xs):

"""Generate the prime numbers, given an iterable of candidate numbers.

Cross off multiples of prime numbers incrementally using iterators."""

table = []

while 1:

x = xs.next()

if table == [] or x < table[0][0]:

yield x

xs, ys = itertools.tee(xs)

timesx = (lambda x: lambda y: x*y)(x)

heapq.heappush(table, (x**2, itertools.imap(timesx, ys)))

else:

while table[0][0] <= x:

heapq.heapreplace(table, (table[0][1].next(), table[0][1]))

def wheel(factors=[2, 3, 5, 7], next=11):

"""Generate the distances between numbers not divisible by a list of small

primes, from the next prime up to the product of the list."""

circumference = reduce(operator.mul, factors)

prev = next

next += 1

end = next + circumference

while next < end:

if not any(next % factor == 0 for factor in factors):

yield next - prev

prev = next

next += 1

def spin(factors=[2, 3, 5, 7], next=11):

"""Generate candidates by making a wheel and cycling through it."""

for gap in itertools.cycle(wheel(factors, next)):

yield next

next += gap

def primes(k=5):

"""Generate primes with the sieve and wheel factorization, which filters

multiples of the first k primes."""

smallprimes = list(itertools.islice(sieve(itertools.count(2)), k + 1))

factors = smallprimes[:-1]

next = smallprimes[-1]

return itertools.chain(factors, sieve(spin(factors, next)))

Labels: haskell, lazy, papers, python

- Delicious Bookmarks
- CiteULike Library
- Amazon Wishlist
- Flickr Photos
- Twitter Tweets
- Last.fm Music
- Google Reader

November 2008 December 2008 January 2009 May 2009 June 2009 July 2009

Subscribe to Posts [Atom]