Sieving prime numbers with Haskell

Question

OK, so I'm trying to write a Haskell program which counts prime numbers extremely fast. Presumably I am not the first person to try to do this. (In particular, I'm damned sure I saw some prior art, but I can't find it now...)

Initially, I want to count the number of primes less than 10^11. Currently I've left my program running for about 15 minutes and it's not even half way there yet. Some rabid C++ programmer claims his program only takes 8 seconds minutes. So clearly I'm doing something horrifyingly wrong.

(In case it matters, my current implementation uses IOUArray Integer Bool and multiple threads to process independent subranges of the search space. Currently it takes several seconds to remove all the multiples of 2 from a 10MB array chunk...)

Note that 10^11 is too big for 32-bit arithmetic. Also, 10^11 bits = 12.5 GB, far too much data to fit into Haskell's 32-bit address space. So you can't have the entire bitmap in memory at once. Finally, note that the number of primes less than 10^11 is just a shade less than 2^32, so there's no way you can store the actual integers all at once either.

---

Edit: Apparently I misread the timing information. What the C++ guy actually claimed was:

• Counting primes < 10^11 takes 8 minutes using just one core, and 56 seconds using 4 cores. (CPU type not specified.)

• Counting primes < 10^10 takes 5 seconds. (Not sure how many cores that's using.)

Sorry about the mistake...

Edit: My source code can be found here: http://hpaste.org/72898

Answer 1

Using the package arithmoi by the excellent StackOverflow teacher Daniel Fischer:

import Math.NumberTheory.Primes.Counting

main = print $ primeCount (10^11)

-- $ time ./arith
-- 4118054813
-- 
-- real 0m0.209s
-- user 0m0.198s
-- sys  0m0.008s

Which is 40 times faster than whatever your 'rabid' C++ friend has written; maybe he can learn a thing or two looking at the Haskell source ... Here are the haddocks