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

[Will Ness]

Steve <stevech1097 <at> yahoo.com.au> writes:

> 
> On Tue, 2009-11-03 at 10:52 -0500, Will wrote:
> > I've just tried it and it was twice slower than mine. (?) I didn't use
> > the [Int]
> > signature in both. [...] It runs twice as fast with it).
> > Although your
> > code has an advantage that it is very easy to add the wheel
> > optimization to it.
> 
> I used [Int] for both. If you didn't use [Int] then it defaults to
> [Integer] and you are probably testing the speed of GMP integer
> operations (rather than the speed of Haskell Int operations) which could
> give differing conclusions.

When both are declared [Int], the ratios are [1.50, 1.40, 1.35, 1.26, 1.26] for 
speed of your version vs mine in producing 100,000, 300,000, 1, 2 and 3 million 
primes, on my laptop, with memory consistently at 120% (as reported by GHCi 
with :s +s switch). Haven't tried any above that, as it's old and slow. But 
clearly the two versions are on par with each  other. The reason I prefer my 
version is that it's in a form easy to be tweaked with further. :)


> I had looked into using a wheel before. Its nice in theory, but not so
> useful in practice. At least that's my experience where using a wheel
> made the primes function slower.

interesting.


> Adding your code and conclusions to "Prime numbers" on the Haskell wiki,
> could be useful.
> http://www.haskell.org/haskellwiki/Prime_numbers

Thank you for pointing me to that page. I've just done that. :) The short 
description that I've arrived at in the end, is that my version explicitly uses 
successive prefixes of the primes list to test batches of odds between 
successive squares of primes. Now it's short and clear.

Thanks!


> I've just updated the page to split it into "Finding Primes" and
> "Testing Primality".
> 
> Steve
>