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

[Will Ness]

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!

I've found Matthew Brecknell's fast code in old Melissa O'Neill's article here
from 2007-02-19 18:14:23 GMT. Without the type signature, it's twice slower than
my code. 

I think it is a fairly faithful translation now of what the sieve is all about,
except that it tests its candidate numbers whereas sieve counts over them (and
thus is able to skip over primes without testing them). The usual functional
approach has it working with each number in isolation, so tests it (to recreate
counting state in effect), thus overworks much on primes.

Next logical step is to start counting!


:)



> Jason
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>