[Haskell-cafe] Re: Simple FAST lazy functional primes
will_n48 at yahoo.com
Thu Nov 5 20:43:00 EST 2009
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.
> Adding your code and conclusions to "Prime numbers" on the Haskell wiki,
> could be useful.
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.
> I've just updated the page to split it into "Finding Primes" and
> "Testing Primality".
More information about the Haskell-Cafe