Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Performance of Prime Generator (Ertugrul S?ylemez)
----------------------------------------------------------------------
Message: 1
Date: Tue, 24 Jan 2012 13:50:32 +0100
From: Ertugrul S?ylemez <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Daniel Fischer <[email protected]> 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-0001.pgp>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 43, Issue 29
*****************************************
