[Haskell-beginners] Performance of Prime Generator

[Daniel Fischer]

On Saturday 21 January 2012, 23:18:23, Ertugrul Söylemez wrote:
> Zhi-Qiang Lei <zhiqiang.lei at gmail.com> wrote:
> > Well, thanks, so far I have tried wheel only and Sieve of Eratosthenes
> > only approaches. They both failed. When the numbers is between
> > 999900000 and 1000000000, they can take more than a hour on my laptop.

They shouldn't. But you have to use the right data structures.

For a prime sieve, you need unboxed mutable arrays if you want it to be 
fast. You can use STUArrays from Data.Array.ST or mutable unboxed vectors 
from Data.Vector.Mutable.Unboxed.

In principle you could also do the sieving in C and use the FFI, but afair 
SPOJ only accepts single source files.

A decent sieve should sieve up to 10^9 in less than 30 seconds. A good 
sieve less than 10.

But that's still too slow, there is a trick you have to use. To find the 
primes in the range from m to n, you don't need to find all primes below m.
(No more hints to not completely spoil the problem.)

> 
> Indeed, you're right.  The method is too slow for numbers of that scale.

No, works fine with the right trick.

> I suggest trying the Sieve of Atkin, which performs quadratically faster
> than the Sieve of Eratosthenes.

No, the complexities differ by a factor of about log (log n) (details 
depend on the implementations).

Without the hinted-at trick, an Atkin sieve would also need to be heavily 
optimised to stand a chance of meeting the time limit. Don't forget that 
the machines used by SPOJ are slow (and on top of that, SPOJ uses ghc-6.10, 
which is far less good at optimising such computations than 6.12 and the 
7.x series).

> 
> I haven't tried it, but an equivalent C implementation can easily
> compute the first 10^9 prime numbers within seconds.

You mean the primes up to 10^9 here?

For the heavily optimised primegen by D. Bernstein, the first 10^9 primes 
take 31.6 seconds here when customised to exploit the full L1 cache; 46 
seconds with the vanilla block size. My segmented Eratosthenes sieve takes 
83.5 seconds for that (but it overtakes primegen for somewhat higher 
limits).

For the primes up to 10^9, the times are 0.675/1.378s for primegen, 3.29s 
for Eratosthenes.

Based on my (limited) experience with the SPOJ machines, I'd estimate that 
primegen would take about 10 seconds there to sieve up to 10^9.

Cheers,
Daniel