<br><br><div class="gmail_quote">On Mon, Nov 2, 2009 at 2:40 PM, Will Ness <span dir="ltr"><<a href="mailto:will_n48@yahoo.com">will_n48@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Jason Dagit <dagit <at> <a href="http://codersbase.com" target="_blank">codersbase.com</a>> writes:<br>
<div class="im"><br>
> On Mon, Nov 2, 2009 at 1:59 PM, Will Ness <will_n48 <at> <a href="http://yahoo.com" target="_blank">yahoo.com</a>> wrote:<br>
> Will Ness <will_n48 <at> <a href="http://yahoo.com" target="_blank">yahoo.com</a>> writes:<br>
><br>
</div><div class="im">> One _crucial_ tidbit I've left out: _type_signature_.<br>
> Adding (:: [Int]) speeds this code up more than TWICE!<br>
> :) :)<br>
><br>
><br>
> If you are okay with Int, then maybe you're also happy with Int32 or Word32.<br>
If so, why don't you use template haskell to build the list at compile time?<br>
If you do that, then getting the kth prime at run-time is O(k). Take that<br>
AKS! :)<br>
><br>
<br>
<br>
</div>O(k), I've removed it since the post actually. Wasn't thinking clearly for a<br>
moment, having seen the double speedup!<br></blockquote><div><br></div><div>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.</div>
<div><br></div><div>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:</div><div><a href="http://book.realworldhaskell.org/read/profiling-and-optimization.html">http://book.realworldhaskell.org/read/profiling-and-optimization.html</a></div>
<div><br></div><div>Good luck!</div><div>Jason</div></div>