<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal>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 (<a href="http://www.haskell.org/haskellwiki/Prime_numbers">http://www.haskell.org/haskellwiki/Prime_numbers</a>)
has a number of implementations, but the faster they get, the longer and uglier
they become.<o:p></o:p></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal>Since it’s such a common problem I’d say it
would be a good idea to add a package to Hackage that exports<o:p></o:p></p>
<p class=MsoNormal>primes :: [Integer]<o:p></o:p></p>
<p class=MsoNormal>and hides the ugly implementation details. Data.Numbers.Primes
seems a logical choice for the namespace, but I’m open to suggestions.<o:p></o:p></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal>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?<o:p></o:p></p>
</div>
</body>
</html>