Project euler 10 - [haskell] Why so inefficient?

Question

Alright, so i've picked up project euler where i left off when using java, and i'm at problem 10. I use Haskell now and i figured it'd be good to learn some haskell since i'm still very much a beginner.

http://projecteuler.net/problem=10

My friend who still codes in java came up with a very straight forward way to implement the sieve of eratosthenes:

http://puu.sh/5zQoU.png

I tried implementing a better looking (and what i thought was gonna be a slightly more efficient) Haskell function to find all primes up to 2,000,000. I came to this very elegant, yet apparently enormously inefficient function:

primeSieveV2 :: [Integer] -> [Integer]
primeSieveV2 [] = []
primeSieveV2 (x:xs) = x:primeSieveV2( (filter (\n -> ( mod n x ) /= 0) xs) )

Now i'm not sure why my function is so much slower than his (he claim his works in 5ms), if anything mine should be faster, since i only check composites once (they are removed from the list when they are found) whereas his checks them as many times as they can be formed.

Any help?

Answer 1

You don't actually have a sieve here. In Haskell you could write a sieve as

import Data.Vector.Unboxed hiding (forM_)
import Data.Vector.Unboxed.Mutable
import Control.Monad.ST (runST)
import Control.Monad (forM_, when)
import Prelude hiding (read)

sieve :: Int -> Vector Bool
sieve n = runST $ do
  vec <- new (n + 1) -- Create the mutable vector
  set vec True       -- Set all the elements to True
  forM_ [2..n] $ \ i -> do -- Loop for i from 2 to n
    val <- read vec i -- read the value at i
    when val $ -- if the value is true, set all it's multiples to false
      forM_ [2*i, 3*i .. n] $ \j -> write vec j False
  freeze vec -- return the immutable vector

main = print . ifoldl' summer 0 $ sieve 2000000
  where summer s i b = if b then i + s else s

This "cheats" by using a mutable unboxed vector, but it's pretty darn fast

$ ghc -O2 primes.hs
$ time ./primes
  142913828923
  real: 0.238 s

This is about 5x faster than my benchmarking of augustss's solution.

Answer 2

To actually implement the sieve efficiently in Haskell you probably need to do it the Java way (i.e., allocate a mutable array an modify it).

For just generating primes I like this:

primes = 2 : filter (isPrime primes) [3,5 ..]
  where isPrime (p:ps) x = p*p > x || x `rem` p /= 0 && isPrime ps x

And then you can print the sum of all primes primes < 2,000,000

main = print $ sum $ takeWhile (< 2000000) primes

You can speed it up by adding a type signature primes :: [Int]. But it works well with Integer as well and that also gives you the correct sum (which 32 bit Int will not).

See The Genuine Sieve of Eratosthenes for more information.