Re: [Haskell-cafe] haskell.org

So how about this: Leave the example. But change the blurb to say: This is inspired by the Sieve of Eratosthenes. For a true Sieve of Eratosthenes, see [link to O'Neil]. On Tue, Apr 21, 2015 at 6:43 AM, David Feuer wrote:

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.

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 https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf and her actual implementation (much better than the one described directly in the paper) is at https://hackage.haskell.org/package/NumberSieves/docs/Math-Sieve-ONeill.html . 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.

On Mon, Apr 20, 2015 at 9:11 PM, Ertugrul Söylemez wrote:

...

...

...

I'd like to note that the prime "sieve" example that is sitting at the top of the homepage is not a real sieve [...]

My understanding is that it *is* a sieve, just not the Sieve of Eratosthenes (because it's a bit hard to fit that into that small little sample box up the top of the page :p).

The main characteristic of a sieve is that it does not divide and that it eliminates all multiples of a prime without a test. Check one bit, eliminate many.

In general if you see any of `mod`, `div` and friends, then it's very unlikely to be a sieve. The only real advantage of the example is that it uses shared primes to use trial division only against primes (instead of probable primes). This gives a slight speedup at the expense of needing a lot of memory.

Greets, Ertugrul

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe