On Mon, Nov 2, 2009 at 2:40 PM, Will Ness
<will_n48@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:
Good luck!
Jason