Programming Praxis – Sieve Of Euler

In today’s Programming Praxis exercise, our goal is to implement the Sieve of Euler to generate primes. Let’s get started, shall we?

Some imports:

import Data.List.Ordered
import Data.Time.Clock

Euler’s sieve is pretty simple: just filter out all remaining multiples of each successive prime number. We add the minor optimization of only considering odd numbers.

primes_euler :: [Integer]
primes_euler = 2 : euler [3,5..] where
    euler ~(x:xs) = x : euler (minus xs $ map (* x) (x:xs))

To compare, we use the Sieve of Eratosthenes implementation found here:

primes_eratosthenes :: [Integer]
primes_eratosthenes = 2 : 3 : sieve (tail primes_eratosthenes) 3 [] where
    sieve ~(p:ps) x fs = let q=p*p in
        foldr (flip minus) [x+2,x+4..q-2] [[y+s,y+2*s..q] | (s,y) <- fs]
        ++ sieve ps q ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])

A quick and dirty benchmarking function:

benchPrimes :: Num a => [a] -> IO ()
benchPrimes f = do start <- getCurrentTime
                   print . sum $ take 10000 f
                   print . flip diffUTCTime start =<< getCurrentTime

Time to run the benchmarks.

main :: IO ()
main = do benchPrimes primes_eratosthenes
          benchPrimes primes_euler

The sieve of Eratosthenes runs in about 0.02 seconds, while Euler’s sieve takes around 6.6 seconds, which means this implementation of Euler’s Sieve is about 300-400 times slower. Clearly you don’t want to use this version in practice.

About these ads

Tags: , , , , , , , , ,

3 Responses to “Programming Praxis – Sieve Of Euler”

  1. cldy Says:

    I’m Haskell newbie and I was wondering why did you used ‘~’ in definitions of ‘euler’ and ‘sieve’? As far as I know this is lazy pattern matching but I failed to understand where to use it and why.

  2. Remco Niemeijer Says:

    Correct, the ~ indicates lazy pattern binding. More importantly, it also makes the pattern irrefutable. Normally, defining a function f (x:xs) = … will produce a warning at compile time saying that the matches for f are non-exhaustive (since f [] is not defined). You could of course fix this by adding something like f [] = undefined, but that adds a useless line of code. I prefer to use ~ when I know a function will only over be applied to an infinite list. It means that it will always try to match the given pattern, producing a run-time error if it can’t. This gets rid of the compiler warning without needless extra code. For more information, see http://www.haskell.org/tutorial/patterns.html#tut-lazy-patterns

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: