[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was:
Optimizationfun]
Claus Reinke
claus.reinke at talk21.com
Tue Feb 20 10:17:48 EST 2007
i have to say that i find the folklore sieve quite acceptable as a sieve, whereas
the faster test-against-primes is obviously different. but the discussion has
prompted me to write yet another sieve, perhaps more acceptable to purists.
instead of using (mod p) repeatedly and filtering directly, we zero out
multiples of p, for all p, then filter out non-zero elements in a second phase:
primes = 2 : filter (>2) (foldr sieve id primes [0..])
-- start sieve for p at position p*p, zeroing position off=(p-1)*(p-1)
sieve p f xs@(off:_) = 0: tail (applyAt (p*p-off) (f . sieve' p) xs)
-- zero positions that are multiples of p
sieve' p = applyAt p (\(_:b)->sieve' p (0:b))
-- like splitAt, followed by (++), where only suffix is operated on
-- infinite lists, non-negative offset
applyAt 0 f xs = f xs
applyAt n f (x:xs) = x:applyAt (n-1) f xs
it seems to be a lot faster than the folklore sieve, and within a factor of 2
of the faster test-against-primes (given the repeated use of applyAt, I guess
it could be sped up further by using a piecewise contiguous list representation,
aka polymorphic ByteString).
claus
More information about the Haskell-Cafe
mailing list