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

Jason Dagit dagit at codersbase.com
Mon Nov 2 18:48:37 EST 2009

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

> Jason Dagit <dagit <at> codersbase.com> writes:
> > 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:
> >
> > 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!  :)
> >
> O(k), I've removed it since the post actually. Wasn't thinking clearly for
> a
> moment, having seen the double speedup!

By the way, do you understand where the speedup with Int is coming from?  As
I understand it, there are two main places.  One is that the type class
dictionary passing can be removed (GHC might figure this out already, I'd
need to check the core to be sure).  The other is that GHC is likely
unboxing to it's primitive Int# type.

If none of that made sense, or you'd like to know how you can double check
what I'm talking about, then Real-World Haskell has a chapter with an

Good luck!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091102/75e34028/attachment.html

More information about the Haskell-Cafe mailing list