[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness:
> > ... There are two attempts to eliminate 45.
>
> I would say there are two requests to not have 45 in the output.
>
Thers are many possible ways to phrase it.

> > > I don't see any problem here. As Melissa (and yourself, I think) have
> > > shown, double hits on multiples are few and far between.
> >
> > It's not a problem, it just means it's not Euler's sieve, because that
> > attempts to eliminate each composite exactly once.
>
> yes I see now. My bad. Wasn't reading that wikipedia page with enough
> attention to detail. It uses the modified (culled, so far) numbers to find
> out the next multiples to be eliminated,

Minor factual error, no big deal.

> not just the prime itself like my code does.

Which is operationally far better because it's much simpler :)

>
> You solution is indeed, exponential:
>
>   euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks)
>   primes = 2:euler [3,5..]
>
>
>   primes
>    = 2:euler (as@[3,5..])
>        3:euler (bs@(tail as `minus` map (3*) as))
>          5:euler (cs@(tail bs `minus` map (5*) bs))
>
>
> There are two separate look-back pointers to /as/ in /bs/, and there are
> two such in /cs/, to /bs/. The book-keeping machinery explodes.
>
> > > Also, it uses no filters, i.e. no individual number divisibility
> > > testing. The "filters" refers first of all to testing an individual
> > > number to decide whether to keep it in or not.
> >
> > Umm, the postponed filters says keep everything until p^2, then eliminate
> > (filter out, remove) multiples of p in the remainder, after that, pick
> > next prime.
> > That's precisely what the above does. It doesn't do the filtering out by
> > divisibility testing but by minus (hence more efficiently). I would say
> > that's a variant of the postponed filters.
>
> Filter is usually (as in Haskell's 'filter') is about testing individual
> elements by a predicate function. There is of course a filtering effect in
> two lists elts' comparison that 'minus' performs, so that's debatable. Even
> the PQ code performs "filtering" in this wider sense.
>

I understood the 'filters' in postponed filters in that wider sense. And I would also find 
it perfectly acceptable to say that the PQ code filters out the composites from the 
stream. Of course if you're used to using 'filter' only in the stricter sense, you 
wouldn't call the `minus` thing a variant of the postponed filters.


>
> not just primes - all the composites not yet removed, too.

Between p and p^2, there are only primes left, fortunately.

> So it can't even be implemented on shared mutable storage if we
> want to delay the removal (as we must, in unbounded case) -

Yes. And it's not nice in the bounded case either.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100105/6af47159/attachment-0001.html