Steve
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