<div dir="ltr"><div>If you want to use bit fiddly mutable vector stuff to make the classic Sieve of Eratosthenes fast and compact, I think it makes a lot of sense to use the bitvec package instead of doing the bit fiddling by hand.<br><br>On the other hand, I think the O'Neill prime sieve makes an excellent example, much prettier than a mutable-vector-based sieve. Her paper is at <a href="https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a> and her actual implementation (much better than the one described directly in the paper) is at <a href="https://hackage.haskell.org/package/NumberSieves/docs/Math-Sieve-ONeill.html">https://hackage.haskell.org/package/NumberSieves/docs/Math-Sieve-ONeill.html</a> . It can be optimized in various ways, most obviously by specializing from Integral to Word, but probably also by switching from a tree-based heap to one based on a mutable vector. I'm not sure how a really carefully optimized version would compare to Eratosthenes.<br></div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Apr 20, 2015 at 9:11 PM, Ertugrul Söylemez <span dir="ltr"><<a href="mailto:ertesx@gmx.de" target="_blank">ertesx@gmx.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">>> I'd like to note that the prime "sieve" example that is sitting at<br>
</span>>> the top of the homepage is not a real sieve [...]<br>
<span class="">><br>
> My understanding is that it *is* a sieve, just not the Sieve of<br>
> Eratosthenes (because it's a bit hard to fit that into that small<br>
> little sample box up the top of the page :p).<br>
<br>
</span>The main characteristic of a sieve is that it does not divide and that<br>
it eliminates all multiples of a prime without a test.  Check one bit,<br>
eliminate many.<br>
<br>
In general if you see any of `mod`, `div` and friends, then it's very<br>
unlikely to be a sieve.  The only real advantage of the example is that<br>
it uses shared primes to use trial division only against primes (instead<br>
of probable primes).  This gives a slight speedup at the expense of<br>
needing a lot of memory.<br>
<br>
<br>
Greets,<br>
Ertugrul<br>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>