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

[Jason Dagit]

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
example:
http://book.realworldhaskell.org/read/profiling-and-optimization.html

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