[Haskell-cafe] Looking for the fastest Haskell primes algorithm
Edward Kmett
ekmett at gmail.com
Tue Apr 14 09:05:41 EDT 2009
You might want to start with the Sieve of Atkin:
http://en.wikipedia.org/wiki/Sieve_of_Atkin
-Edward
On Tue, Apr 14, 2009 at 8:40 AM, Niemeijer, R.A. <r.a.niemeijer at tue.nl>wrote:
> Today I happened to need a large list of prime numbers. Obviously this is
> a well-known problem, so I figured there would be something on Hackage that
> I could use. Surprisingly, there isn’t, or if there is it’s not easy to
> find. Searching for prime or primes on Hackage reveals nothing. Searching
> for primes on Hayoo gives Codec.Encryption.RSA.NumberTheory, but that uses
> the inefficient one-liner implementation. The HaskellWiki article on primes
> (http://www.haskell.org/haskellwiki/Prime_numbers) has a number of
> implementations, but the faster they get, the longer and uglier they become.
>
>
>
> Since it’s such a common problem I’d say it would be a good idea to add a
> package to Hackage that exports
>
> primes :: [Integer]
>
> and hides the ugly implementation details. Data.Numbers.Primes seems a
> logical choice for the namespace, but I’m open to suggestions.
>
>
>
> The trick then is to find the most efficient implementation of primes. The
> Haskell wiki article mentions ONeillPrimes.hs as one of the fastest ones,
> but maybe there’s a faster version. So my question is: does anybody know
> what the fastest Haskell algorithm for generating primes is?
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090414/39a8be23/attachment.htm
More information about the Haskell-Cafe
mailing list