david.feuer at gmail.com
Tue Apr 21 03:43:05 UTC 2015
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)
. 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 <ertesx at gmx.de> 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.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe