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 |
In reply to this post by Malcolm Reynolds
On 11/23/2008, "Malcolm Reynolds" <[hidden email]> wrote:
>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. |
In reply to this post by Malcolm Reynolds
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 |
In reply to this post by Malcolm Reynolds
On Sun, Nov 23, 2008 at 5:28 PM, Malcolm Reynolds
<[hidden email]> wrote: > 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. |
Free forum by Nabble | Edit this page |