# Tutorial :Haskell: faster summation of primes ### 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
Previous
Next Post »