###

Question:

Disclaimer: I'm working on Euler Problem 9.

I'm adding up some pretty large numbers, all the primes from 1 to 2 000 000.

Summing those primes takes forever. I'm using the haskell built in function 'sum'.

as in:

`sum listOfPrimes `

Are there any other faster options?

--My prime generator was the slow link in my code.

###

Solution:1

It sounds like your problem is not summing the numbers, but generating them. What is your implementation of listOfPrimes?

This paper may be of interest: http://lambda-the-ultimate.org/node/3127

###

Solution:2

I'm hoping you are using ghc -O2 and not ghci, right? Your problem will be in the generation, not the summation.

One faster way is to use stream fusion-based sequences, which optimize better. With regular lists:

`import Data.List import qualified Data.Map as M primes :: [Integer] primes = mkPrimes 2 M.empty where mkPrimes n m = case (M.null m, M.findMin m) of (False, (n', skips)) | n == n' -> mkPrimes (succ n) (addSkips n (M.deleteMin m) skips) _ -> n : mkPrimes (succ n) (addSkip n m n) addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m addSkips = foldl' . addSkip -- fuse: main = print (sum (takeWhile (<= 2000000) primes)) `

We get,

`$ ghc -O2 --make A.hs $ time ./A 142913828922 ./A 9.99s user 0.17s system 99% cpu 10.166 total `

Switching to streams, so sum . takeWhile fuses:

`import qualified Data.List.Stream as S main = print (S.sum (S.takeWhile (<= 2000000) primes)) `

Saves some small time,

`$ time ./A 142913828922 ./A 9.60s user 0.13s system 99% cpu 9.795 total `

But your problem will be prime generation, as we can see if we discard the summation altogether, replacing sum with last:

`$ time ./A 1999993 ./A 9.65s user 0.12s system 99% cpu 9.768 total `

So find a better prime generator. :-)

Finally, there's a library on Hackage for fast prime generators:

http://hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html

Using it, our time becomes:

`$ cabal install primes $ cabal install stream-fusion $ cat A.hs import qualified Data.List.Stream as S import Data.Numbers.Primes main = print . S.sum . S.takeWhile (<= 2000000) $ primes $ ghc -O2 -fvia-C -optc-O3 A.hs --make $ time ./A 142913828922 ./A 0.62s user 0.07s system 99% cpu 0.694 total `

###

Solution:3

The slow part of your function is for sure the generating of the primes, not the `sum`

function. A nice way to generate primes would be:

`isprime :: (Integral i) => i -> Bool isprime n = isprime_ n primes where isprime_ n (p:ps) | p*p > n = True | n `mod` p == 0 = False | otherwise = isprime_ n ps primes :: (Integral i) => [i] primes = 2 : filter isprime [3,5..] `

I think it's very readable, though maybe a bit surprising that it works at all because it uses recursion and laziness of the `primes`

list. It's also rather fast, though one could do further optimizations at the expense of readability.

###

Solution:4

I wrote a "Sieve of Eratosthenes" here:

`import Data.List import qualified Data.Map as M primes :: [Integer] primes = mkPrimes 2 M.empty where mkPrimes n m = case (M.null m, M.findMin m) of (False, (n', skips)) | n == n' -> mkPrimes (succ n) (addSkips n (M.deleteMin m) skips) _ -> n : mkPrimes (succ n) (addSkip n m n) addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m addSkips = foldl' . addSkip `

Using this, it takes about 25s to `print . sum $ takeWhile (<= 20000000)`

on my desktop. Could be better? Sure, it takes J under 1 second to run

+/p:i.p:^:_1]20000000 12272577818052

but it has a pretty optimized prime number generator.

**Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com**

EmoticonEmoticon