[Haskell-cafe] haskell.org

[Yitzchak Gale]

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 <david.feuer at gmail.com> 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 <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.
>>
>>
>> Greets,
>> Ertugrul
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>