[Haskell-beginners] Performance of Prime Generator
es at ertes.de
Tue Jan 24 13:50:32 CET 2012
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 . 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".
> > 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.
nightmare = unsafePerformIO (getWrongWife >>= sex)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 836 bytes
Desc: not available
More information about the Beginners