I'd like to bring the thread that began with a question about ``why
the "classic sieve" example did so badly when compared to "a C
implementation of the same thing"'' back to its starting point. In
the discussion that ensued, various people have spoken about various
algorithms to find primes. I've mentioned my own, and claimed it was
a more faithful rendition of the Sieve of Eratosthenes in a
functional setting (where we like to generalize it to produce a lazy
and infinite list) than the classic one-liner.
But talk is cheap. What about some actual numbers, and some code for
some actual implementations...?
I've put together an archive of all the code we've talked about, and
put it at
http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip
Here are some performance measurements of the primes algorithms we've
been discussing, with the task of finding the 1000th prime (7919),
the 10,000th prime (104729), the 100,000th prime (1299709) and the
1,000,000th prime (15485863). The times are with GHC on my PowerMac G5.
(this table best viewed in a fixed-width font!)
--------------------------------------------------------
Time (s) for Number of Primes
------------------------------------------
Algorithm 10^3 10^4 10^5 10^6 10^7
--------------------------------------------------------
O'Neill (#2) 0.01 0.09 1.45 22.41 393.28
O'Neill (#1) 0.01 0.14 2.93 47.08 -
"sieve" (#3) 0.01 0.25 7.28 213.19 -
Naive 0.32 0.66 16.04 419.22 -
Runciman 0.02 0.74 29.25 - -
Reinke 0.04 1.21 41.00 - -
Gale (#1) 0.12 17.99 - - -
"sieve" (#1) 0.16 32.59 - - -
"sieve" (#2) 0.01 32.76 - - -
Gale (#2) 1.36 268.65 - - -
--------------------------------------------------------
Notes:
- The dashes in the table mean "I gave up waiting" (i.e., > 500 seconds)
- "sieve" (#1) is the classic example we're all familiar with
- "sieve" (#2) is the classic example, but sieving a list without
multiples of 2,3,5, or 7 -- notice how it makes no real difference
- "sieve" (#3) is the classic example, but generating a lazy-but-
finite list (see below)
- O'Neill (#1) is the algorithm of mine discussed in http://
www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- O'Neill (#2) is a variant of that algorithm that generates a lazy-
but-finite list of primes.
- Naive is the the non-sieve-based "divide by every prime up to the
square root" algorithm for finding primes
- Runciman is Colin Runciman's algorithm, from his _Lazy Wheel Sieves
and Spirals of Primes_ paper
- Reinke is the ``applyAt'' algorithm Claus Reinke posted here
- Gale (#1) is Yitz Gale's deleteOrd algorithm
- Gale (#2) is Yitz Gale's crossOff algorithm
Returning to where we began, if you want to calculate primes in
Haskell, there are ways to do it -- ways based on the Sieve of
Eratosthenes -- where you don't have to feel too bad about the
performance of functional programs.
Melissa.
P.S. Here's the code for a "sieve" (#3) style prime finder.
primesToLimit :: Integer -> [Integer]
primesToLimit limit = 2 : lsieve [3,5..] where
lsieve ps@(p : xs)
| p < sqrtlimit = p : lsieve [x | x <- xs, x `mod` p > 0]
| otherwise = takeWhile (<= limit) ps
where
sqrtlimit = round (sqrt (fromInteger limit))
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
