[Haskell-beginners] Performance of Prime Generator
Daniel Fischer
daniel.is.fischer at googlemail.com
Sun Jan 22 23:57:52 CET 2012
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
More information about the Beginners
mailing list