Primary sieve leads to stack overflow (I'm about to)
For an euler project, I was looking for a way to implement the Eratosthenes sieve because I expected it to be faster than my original implementation (and it is necessary). I came up with this function:
sieve :: Int -> [Int] -> [Int]
sieve p (x:xs) | rem x p == 0 = sieve p xs
| otherwise = x : (sieve x $ sieve p xs)
sieve _ [] = []
Which works, but hits the fan very quickly causing a stack overflow. I headed here for some advice and immediately came across a spoiler that looks exactly the same to me, but the performance difference is unusual. I still want to keep using my own implementation and would like to know if my function can be easily changed to use less memory.
source to share
Your code has an exponential burst inside it:
sieve p (x:xs) | rem x p == 0 = sieve p xs
| otherwise = x : (sieve x $ sieve p xs)
-- ^^^^^^^ here!
-- ^^^^^^^ and here!
You want to use an inner call sieve
to continue filtering with p
, but since you are using the same function sieve
, it also fires new filters for new primes when they encounter them, but this is completely redundant since the "top" call level also triggers a new one filter for the same simple!
sieve 2 [3..]
= 3 : sieve 3 (sieve 2 [4..])
= 3 : sieve 3 (5 : sieve 5 (sieve 2 [6..]))
= 3 : 5 : sieve 5 (sieve 3 (sieve 5 (sieve 2 [6..])))
.... -- ^^^ ^^^ -- !!!
After 7 passes to the top through four sieve
here, each will split in two, creating four new sieve 7
s, so there will be eight in the chain sieve
! Worse, when 9 is compound! - passes through the sieves, it separates 2, 7 s and 5 and will only deviate by 3. So this is actually worse than the exponential number of primes n
and close to exponential in the value of the last prime (i.e. ~ n log(n)
).
Change it to
sieve p (x:xs) | rem x p == 0 = sieve p xs
| otherwise = x : (sieve x $ filter ((>0).(`rem` p)) xs)
and you will get a code equivalent to the one you are quoting.
If you prefer to pass the code to everyone, you can introduce a new argument, a boolean flag that determines whether new filters should be run or not:
primes = 2 : sieve True 2 [3..] sieve b p (x:xs) | rem x p == 0 = sieve b p xs | b = x : (sieve b x $ sieve False p xs) | otherwise = x : sieve b p xs
source to share