[Haskell-cafe] Re: Simple FAST lazy functional primes
Jason Dagit
dagit at codersbase.com
Mon Nov 2 16:10:12 EST 2009
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
More information about the Haskell-Cafe
mailing list