[Haskell-beginners] Performance of Prime Generator

[Ertugrul Söylemez]

Daniel Fischer <daniel.is.fischer at googlemail.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.

That's what I've used.  You find the code on hpaste [1].  It's a
carefully optimized Sieve of Eratosthenes and needs around 20 seconds
for the primes up to 10^9.  See the refinement in the annotation, which
I've added just now.  Before that it took around 35 seconds.

I considered that to be "too slow".

[1] http://hpaste.org/56866


> > 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?

Yes, sorry.  And I was referring to the Sieve of Atkin there, but you
are right.  That one is only slightly faster.


Greets,
Ertugrul

-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120124/faedc271/attachment.pgp>