4 ms·

this isn't a sieve, this is trial division. the runtime performance is very different.

gizmo686 13y ago
It is a sieve. Looking at what the function 'sieve' does: sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] The input is a list of numbers, the first of which, p, is guaranteed to be prime. The first element of the output is p. Then, we generate a second list, which contains all of the elements of a input list, except for the multiples of p. And we recourse into the second list. We can make this clear by writing is as: sieve (p:xs) = p:(sieve $ filter (\x -> x `mod` p /= 0) $ xs) In this way, we can see that we are selecting the first element in the list, marking it as a prime (by returning it), and then removing all of the multiples of said prime, before repeating the operation on the new list. That is a literal description of the sieving algorithm. Now, because of lazy evaluation, the sieving function may turn into going through the list one number at a time and performing trial division with all previous primes. From a theoretical perspective, this has the same time complexity (although it would be slower on modern hardware). Using a strict version of filter, the computer (should) literally perform the sieve. It should be noted that by making sieve strict, you loose the ability to generate an infinite list of primes through sieve [2..], as that would never terminate. I believe the standard solution (as with non functional langauses) is to compute the sieve in blocks, so you solve the block the normal way, then when you get to a new block, you first go through all of your known primes and cross them out. Edit: If you do try calling sieve (either strictly or non-strictly) on a finite list, you will need to handle the case of an empty list. Adding "sieve []=[]" in addition to the main definition should work.
- minopret 13y ago
  The disadvantage is how many times the implementation using "mod" is visiting each candidate. This disadvantage is explained at length in "The Genuine Sieve of Eratothenes" (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf preprint of http://dx.doi.org/10.1017%2FS0956796808007004 http://dx.doi.org/10.1017%2FS0956796808007004).

It is a sieve. Looking at what the function 'sieve' does: sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] The input is a list of numbers, the first of which, p, is guaranteed to be prime. The first element of the output is p. Then, we generate a second list, which contains all of the elements of a input list, except for the multiples of p. And we recourse into the second list. We can make this clear by writing is as: sieve (p:xs) = p:(sieve $ filter (\x -> x `mod` p /= 0) $ xs) In this way, we can see that we are selecting the first element in the list, marking it as a prime (by returning it), and then removing all of the multiples of said prime, before repeating the operation on the new list. That is a literal description of the sieving algorithm. Now, because of lazy evaluation, the sieving function may turn into going through the list one number at a time and performing trial division with all previous primes. From a theoretical perspective, this has the same time complexity (although it would be slower on modern hardware). Using a strict version of filter, the computer (should) literally perform the sieve. It should be noted that by making sieve strict, you loose the ability to generate an infinite list of primes through sieve [2..], as that would never terminate. I believe the standard solution (as with non functional langauses) is to compute the sieve in blocks, so you solve the block the normal way, then when you get to a new block, you first go through all of your known primes and cross them out. Edit: If you do try calling sieve (either strictly or non-strictly) on a finite list, you will need to handle the case of an empty list. Adding "sieve []=[]" in addition to the main definition should work.

minopret 13y ago
The disadvantage is how many times the implementation using "mod" is visiting each candidate. This disadvantage is explained at length in "The Genuine Sieve of Eratothenes" (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf preprint of http://dx.doi.org/10.1017%2FS0956796808007004 http://dx.doi.org/10.1017%2FS0956796808007004).