99 questions/Solutions/39

(Difference between revisions)
 Revision as of 10:51, 3 June 2011 (edit)← Previous diff Revision as of 11:23, 3 June 2011 (edit) (undo)Next diff → Line 3: Line 3: Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. - '''Solution 1:''' + '''Solution 1.''' primesR :: Integral a => a -> a -> [a] primesR :: Integral a => a -> a -> [a] Line 11: Line 11: If we are challenged to give all primes in the range between a and b we simply take all numbers from a up to b and filter all the primes through. If we are challenged to give all primes in the range between a and b we simply take all numbers from a up to b and filter all the primes through. - This is good for ''very narrow ranges'' as Q.31's isPrime tests by ''trial division'' using (up to$\sqrt b$) a memoized primes list produced by sieve of Eratosthenes to which it refers internally. So it'll be slower, but immediate. + This is good for ''very narrow ranges'' as Q.31's isPrime tests numbers by ''trial division'' using (up to$\sqrt b$) a memoized primes list produced by sieve of Eratosthenes to which it refers internally. So it'll be slower, but immediate, testing the numbers one by one. + + '''Solution 2.''' + + For ''very wide'' ranges, specifically when $a < \sqrt{b}$, we're better off just using the primes sequence itself, without any post-processing: - '''Solution 2:''' primes :: Integral a => [a] primes :: Integral a => [a] - primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ] + primes = primesTME -- of Q.31 - in sieve [2..] + primesR :: Integral a => a -> a -> [a] primesR :: Integral a => a -> a -> [a] Line 23: Line 25: - Another way to compute the claimed list is done by using the ''Sieve of Eratosthenes''. The primes function generates a list of all (!) prime numbers using this algorithm and primesR filter the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nicely the ''Sieve of Eratosthenes'' can be implemented in Haskell :)] + '''Solution 3.''' + + primesR :: Integral a => a -> a -> [a] + primesR a b = takeWhile (<= b) $dropWhile (< a)$ sieve [2..] + where sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ] + - ''this is of course a famous case of executable specification, with all the implied pitfalls of inefficiency when (ab)used as if it were an actual code''. + Another way to compute the claimed list is done by using the ''Sieve of Eratosthenes''. The sieve [2..] function call generates a list of all (!) prime numbers using this algorithm and primesR filters the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nicely the ''Sieve of Eratosthenes'' can be implemented in Haskell :)] - '''Solution 3:''' + ''this is of course a famous case of (mislabeled) executable specification, with all the implied pitfalls of inefficiency when (ab)used as if it were an actual code''. + + '''Solution 4.''' Use the ''proper'' Sieve of Eratosthenes from e.g. [http://www.haskell.org/haskellwiki/99_questions/Solutions/31 31st question's solution] (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point: Use the ''proper'' Sieve of Eratosthenes from e.g. [http://www.haskell.org/haskellwiki/99_questions/Solutions/31 31st question's solution] (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point: {-# OPTIONS_GHC -O2 -fno-cse #-} {-# OPTIONS_GHC -O2 -fno-cse #-} - -- tree-merging Eratosthenes sieve, primesTME of haskellwiki/prime_numbers, + -- tree-merging Eratosthenes sieve, primesTME of Q.31, -- adjusted to produce primes in a given range (inclusive) -- adjusted to produce primes in a given range (inclusive) primesR a b primesR a b Line 43: Line 52: where where primes' = tail primesTME -- external unbounded list of primes primes' = tail primesTME -- external unbounded list of primes - a' = snapUp (max 3 a) 1 2 + a' = snapUp (max 3 a) 3 2 z = floor $sqrt$ fromIntegral b + 1 z = floor $sqrt$ fromIntegral b + 1 join (xs:t) = union xs (join (pairs t)) join (xs:t) = union xs (join (pairs t)) Line 63: Line 72: ''(This turned out to be quite a project, with some quite subtle points.)'' It should be much better then taking a slice of a full sequential list of primes, as it won't try to generate any primes between the ''square root of b'' and ''a''. To wit, ''(This turned out to be quite a project, with some quite subtle points.)'' It should be much better then taking a slice of a full sequential list of primes, as it won't try to generate any primes between the ''square root of b'' and ''a''. To wit, - > primesR 10100 10200 -- Sol.3 + > primesR 10100 10200 -- Sol.4 [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (5,497 reductions, 11,382 cells) (5,497 reductions, 11,382 cells) - > takeWhile (<= 10200) $dropWhile (< 10100)$ primesTME -- TME of Q.31 + > takeWhile (<= 10200) $dropWhile (< 10100)$ primesTME -- Sol.2 [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (140,313 reductions, 381,058 cells) (140,313 reductions, 381,058 cells) - > takeWhile (<= 10200) $dropWhile (< 10100)$ sieve [2..] -- Sol.2 + > takeWhile (<= 10200) $dropWhile (< 10100)$ sieve [2..] -- Sol.3 where sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ] where sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ] [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] Line 83: Line 92: (testing with Hugs of Nov 2002). (testing with Hugs of Nov 2002). - This solution is faster but not immediate. It has a certain preprocessing stage but then goes on fast to produce the whole range. To illustrate, to produce the 49 primes in 1000-wide range above 120200300100 it takes about 18 seconds on my oldish notebook for the 1st version, with the first number produced almost immediately (~ 0.4 sec); but this version spews up all 49 primes in one go after just under 1 sec. + This solution is faster but not immediate. It has a certain preprocessing stage but then goes on fast to produce the whole range. To illustrate, to produce the 49 primes in 1000-wide range above 120200300100 it takes about 18 seconds on my oldish notebook for the 1st version, with the first number produced almost immediately (~ 0.4 sec); but this version spews out all 49 primes in one go after just under 1 sec. - + - '''Solution 4.''' + - + - For ''very wide'' ranges, specifically when $a < \sqrt{b}$, we're better off just using the primes sequence itself, without any post-processing: + - + - + - primes :: Integral a => [a] + - primes = primesTME -- of Q.31 + - + - primesR :: Integral a => a -> a -> [a] + - primesR a b = takeWhile (<= b) . dropWhile (< a) $primes + - + Revision as of 11:23, 3 June 2011 (*) A list of prime numbers. Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. Solution 1. primesR :: Integral a => a -> a -> [a] primesR a b = filter isPrime [a..b] If we are challenged to give all primes in the range between a and b we simply take all numbers from a up to b and filter all the primes through. This is good for very narrow ranges as Q.31's isPrime tests numbers by trial division using (up to$\sqrt b$) a memoized primes list produced by sieve of Eratosthenes to which it refers internally. So it'll be slower, but immediate, testing the numbers one by one. Solution 2. For very wide ranges, specifically when $a < \sqrt{b}$, we're better off just using the primes sequence itself, without any post-processing: primes :: Integral a => [a] primes = primesTME -- of Q.31 primesR :: Integral a => a -> a -> [a] primesR a b = takeWhile (<= b)$ dropWhile (< a) primes

Solution 3.

primesR :: Integral a => a -> a -> [a]
primesR a b = takeWhile (<= b) $dropWhile (< a)$ sieve [2..]
where sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ]

Another way to compute the claimed list is done by using the Sieve of Eratosthenes. The sieve [2..] function call generates a list of all (!) prime numbers using this algorithm and primesR filters the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nicely the Sieve of Eratosthenes can be implemented in Haskell :)]

this is of course a famous case of (mislabeled) executable specification, with all the implied pitfalls of inefficiency when (ab)used as if it were an actual code.

Solution 4.

Use the proper Sieve of Eratosthenes from e.g. 31st question's solution (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point:

{-# OPTIONS_GHC -O2 -fno-cse #-}
-- tree-merging Eratosthenes sieve, primesTME of Q.31,
--  adjusted to produce primes in a given range (inclusive)
primesR a b
| b<a || b<2 = []
| otherwise  =
(if a <= 2 then [2] else []) ++
gaps a' (join [[x,x+step..b] | p <- takeWhile (<= z) primes'
, let q = p*p ; step = 2*p
x = snapUp (max a' q) q step ])
where
primes' = tail primesTME        -- external unbounded list of primes
a'      = snapUp (max 3 a) 3 2
z       = floor $sqrt$ fromIntegral b + 1
join  (xs:t)    = union xs (join (pairs t))
join  []        = []
pairs (xs:ys:t) = (union xs ys) : pairs t
pairs  t        = t
gaps k xs@(x:t) | k==x  = gaps (k+2) t
| True  = k : gaps (k+2) xs
gaps k []       = [k,k+2..b]
snapUp v origin step = let r = rem (v-origin) step -- rem OK if v>=origin
in if r==0 then v else v+(step-r)
-- duplicates-removing union of two ordered increasing lists
union (x:xs) (y:ys) = case (compare x y) of
LT -> x : union  xs  (y:ys)
EQ -> x : union  xs     ys
GT -> y : union (x:xs)  ys
union  a      b     = a ++ b

(This turned out to be quite a project, with some quite subtle points.) It should be much better then taking a slice of a full sequential list of primes, as it won't try to generate any primes between the square root of b and a. To wit,

> primesR 10100 10200                                            -- Sol.4
[10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193]
(5,497 reductions, 11,382 cells)

> takeWhile (<= 10200) $dropWhile (< 10100)$ primesTME         -- Sol.2
[10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193]
(140,313 reductions, 381,058 cells)

> takeWhile (<= 10200) $dropWhile (< 10100)$ sieve [2..]       -- Sol.3
where sieve (n:ns) = n:sieve [ m | m <- ns, m mod n /= 0 ]
[10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193]
(54,893,566 reductions, 79,935,263 cells, 6 garbage collections)

> filter isPrime [10100..10200]                                  -- Sol.1
[10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193]
(15,750 reductions, 29,292 cells)                        -- isPrime: Q.31

(testing with Hugs of Nov 2002).

This solution is faster but not immediate. It has a certain preprocessing stage but then goes on fast to produce the whole range. To illustrate, to produce the 49 primes in 1000-wide range above 120200300100 it takes about 18 seconds on my oldish notebook for the 1st version, with the first number produced almost immediately (~ 0.4 sec); but this version spews out all 49 primes in one go after just under 1 sec.