[Haskell-cafe] A tale of Project Euler
Andrew Coppin
andrewcoppin at btinternet.com
Tue Nov 27 15:59:39 EST 2007
Brent Yorgey wrote:
> The algorithm you use to compute primes is actually quite inefficient,
> and in particular, it is NOT the same algorithm that the C program is
> using, despite first appearances! The call to 'filter' in the sieve
> function works by checking *every* number for divisibility by p, and
> only keeping those that aren't divisible by p; whereas the C program
> simply marks multiples of p as non-prime, skipping over those which
> are not multiples. So the Haskell version basically searches for
> primes by doing trial division on every single integer, whereas the C
> version is actually using a sieve.
I had to reread that several times to figure out what you're actually
saying.
So the Haskell version tests all N elements to see if P divides them,
whereas the C version loops over an array (roughly) N / P times flagging
the composite numbers, which is why it's so much damn faster. (Since as
P grows, N / P plummets.)
OK, cool. So... now how do I implement this without using mutable
arrays? :-}
PS. The *original* prime number thing I had was much slower. Used an
"is_prime" function to do trial division by *every* number below N. (!!)
The version I showed as much faster than that, but still quite slow, as
you say...
More information about the Haskell-Cafe
mailing list