[Haskell-cafe] Re: Simple FAST lazy functional primes

[Jason Dagit]

On Mon, Nov 2, 2009 at 1:59 PM, Will Ness <will_n48 at yahoo.com> wrote:

> Will Ness <will_n48 <at> yahoo.com> writes:
>
> > primes   = 2: 3: sieve 0 primes' 5
> > primes'  = tail primes
> > sieve k (p:ps) x
> >          = [x | x <- [x,x+2..p*p-2],
> >                  and [(x`rem`p)/=0 | p <- take k primes']]
> >            ++ sieve (k+1) ps (p*p+2)
> >
> > (thanks to Leon P.Smith for his brilliant idea of directly generating
> > the spans of odds instead of calling 'span' on the infinite odds list).
> >
> > The relative performance vs the PQ-version is:
> >
> >   100,000   300,000   1,000,000  primes produced
> >    0.6       0.75      0.97
> >
>
> One _crucial_ tidbit I've left out: _type_signature_.
>
> Adding (:: [Int]) speeds this code up more than TWICE!
>
> :) :)
>

If you are okay with Int, then maybe you're also happy with Int32 or Word32.
 If so, why don't you use template haskell to build the list at compile
time?  If you do that, then getting the kth prime at run-time is O(k).  Take
that AKS!  :)

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091102/bbf9bb7c/attachment.html