Efficient sieve of erastothenes, for solving project euler problem #10?
Hello all, I'm attempting to learn Haskell by going through the project euler problems. Number 10, http://projecteuler.net/index.php?section=problems&id=10 , involves summing prime numbers. It's easy in terms of coding something up that works, but I'm having a lot of trouble getting decent performance. I've learned a reasonable amount of ML at uni but Haskell is the first lazy language I've used.. I think the inefficiency is possibly due to the laziness but I'm not positive. I'd love if someone could show me how to do this in Haskell somewhere near as fast as C - at the moment I have a C version which runs in about a tenth of a second ( http://github.com/malcster/project-euler-solutions--c-/tree/master/10.c ). My haskell attempts are http://github.com/malcster/project-euler-solutions/tree/master/10better.hs (using the sieve) and http://github.com/malcster/project-euler-solutions/tree/master/10.hs (using possibly an even worse method, but seems to be a bit faster). If anyone could point out any neat strictness annotations or anything else I could put in, that would be cool. Cheers, Malcolm
Sorry, I pressed inadvertently the "send" button... The previous code has some typos... :-) The code is this: ------------------------------ isPrime :: Integer -> Bool isPrime n = isPrimeAux n 2 where -- First param is the number to be tested -- for primality. Second param the current -- divisor. isPrimeAux :: Integer -> Integer -> Bool isPrimeAux n k | fromIntegral k > sqrt (fromIntegral n) = True | otherwise = if n `mod` k == 0 then False else isPrimeAux n (k+1) main :: IO () main = print $ sum $ filter isPrime [2..1999999] ------------------------- I compiled the code with "ghc --make prob10.hs", and although it wasn't lightning fast I got the answer after a little less than a minute on my system. Hope it helped, Christos
On 11/23/2008, "Malcolm Reynolds"
Hello all,
I'm attempting to learn Haskell by going through the project euler problems. Number 10, http://projecteuler.net/index.php?section=problems&id=10 , involves summing prime numbers. It's easy in terms of coding something up that works, but I'm having a lot of trouble getting decent performance. I've learned a reasonable amount of ML at uni but Haskell is the first lazy language I've used.. I think the inefficiency is possibly due to the laziness but I'm not positive.
I'd love if someone could show me how to do this in Haskell somewhere near as fast as C - at the moment I have a C version which runs in about a tenth of a second ( http://github.com/malcster/project-euler-solutions--c-/tree/master/10.c ). My haskell attempts are http://github.com/malcster/project-euler-solutions/tree/master/10better.hs (using the sieve) and http://github.com/malcster/project-euler-solutions/tree/master/10.hs (using possibly an even worse method, but seems to be a bit faster).
If anyone could point out any neat strictness annotations or anything else I could put in, that would be cool.
Cheers,
Malcolm
Hi Malcom, I have a solution to Project Euler problem #10 that runs in 7.3 seconds on my computer when compiled with -O2. I am neither a math expert nor a Haskell expert, so others may be able to offer a better solution. module PE010 where import ProjectEuler(primes2) main = putStrLn output output = show result result = sum $ takeWhile (\x -> x < 2000000) primes2 -- This is the relevant stuff from ProjectEuler.hs primes2 :: [Integer] primes2 = getPrime [] primeCandidates where getPrime :: [Integer] -> [Integer] -> [Integer] getPrime ls (x:xs) = let maxDiv = floor $ sqrt $ fromIntegral x in if isDivisibleByAny (takeWhile (\n -> n <= maxDiv) ls) x then getPrime ls xs else x : getPrime (ls ++ [x]) xs primeCandidates = 2 : (oddsFrom 3) oddsFrom n | odd n = [n, n+2 ..] | otherwise = [n+1, n+3 ..] isDivisibleByAny ls n = or $ map (\d -> n `mod` d == 0) ls I didn't get a chance to look at your version, but obviously, 7.3 seconds is a lot slower than the 0.1 seconds you saw with your C version.
Malcolm Reynolds wrote:
I'm attempting to learn Haskell by going through the project euler problems. Number 10, http://projecteuler.net/index.php?section=problems&id=10 , involves summing prime numbers. It's easy in terms of coding something up that works, but I'm having a lot of trouble getting decent performance.
See also http://haskell.org/haskellwiki/Prime_numbers Note that your C version uses a different algorithm than your Haskell version, the former uses an array with random access while the latter uses a linked list. Regards, apfelmus
On Sun, Nov 23, 2008 at 5:28 PM, Malcolm Reynolds
Hello all,
I'm attempting to learn Haskell by going through the project euler problems. Number 10, http://projecteuler.net/index.php?section=problems&id=10 , involves summing prime numbers. It's easy in terms of coding something up that works, but I'm having a lot of trouble getting decent performance.
I realize that these early prime number related Euler problems are about writing your own efficient prime generator, so you may want to ignore this message for now. But later on when the problems just happen to involve primes, but the generator is kind of assumed, you may want to check out this collection: http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip The file "ONeillPrimes.hs" contains what is, I think, generally considered to be one of the fastest pure-Haskell prime generators. In particular, this program:
import ONeillPrimes ( primesToLimit )
main = ( print . sum . primesToLimit ) 2000000
Gives the correct answer on my machine in about 0.3 seconds.
participants (5)
-
apfelmus -
Christos Chryssochoidis -
David Frey -
Kurt Hutchinson -
Malcolm Reynolds