Efficient sieve of erastothenes, for solving project euler problem #10?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Efficient sieve of erastothenes, for solving project euler problem #10?

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
Reply | Threaded
Open this post in threaded view
|

Efficient sieve of erastothenes, for solving project euler problem #10?

Christos Chryssochoidis
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
Reply | Threaded
Open this post in threaded view
|

Efficient sieve of erastothenes, for solving project euler problem #10?

David Frey
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.
Reply | Threaded
Open this post in threaded view
|

Re: Efficient sieve of erastothenes, for solving project euler problem #10?

Heinrich Apfelmus
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

Reply | Threaded
Open this post in threaded view
|

Efficient sieve of erastothenes, for solving project euler problem #10?

Kurt Hutchinson
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.