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...
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
