
On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng
Recently, I'm trying to solve some problems in project euler using haskell. When it came to problem 10, calculating the sum of all primes below 20000000, I try to write a program which can generate primes. In my memory Eratosthenes is faster than just whether a number can be divided by the number less then the square root of it. Firstly, I wrote the following programs:
module Main where isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x) isPrime' d target maxd | d > maxd = True | mod target d == 0 = False | otherwise = isPrime' (d + 2) target maxd
main = print $ (sum (filter isPrime [3,5..2000000]) + 2)
And it consume about 11s in my computer. Then, I tried to figure out how to solve the problem by Eratosthenes, but failed. Later, I find a program implemented by others, meeting my purpose and I've used it to solve the problem:
primes :: [Int] primes = primes' [2..]
primes' :: [Int] -> [Int] primes' [] = [] primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
solve x = sum $ primes' [2..x]
main = print $ solve 2000000
Well, although the code is beautiful, it is slow. Even waiting for a minute, no answer was printed.
In C version, Eratosthenes is faster than the method implemented in my earlier code, which only consume 0.3s(the earlier method consume 1.6s).
So I want to know, why Eratosthenes implemented in Haskell is slow than the ugly code implemented by me. Could anyone tell me?
Eratosthenes's complexity is O(n^2) (both space and time), whereas the "ugly" one has a sub-quadratic running complexity and linear in space. Try to profile them: $> ghc -O2 --make -prof -auto-all <filename> $> ./primes +RTS -p -hc $> hp2ps primes.hp You'll see that most of the time is spent allocating space which is never released. You could play a bit with strictness, but the main problem is the awful complexity of the algorithm. hth, L.
Thank you Yi Cheng
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners