As a student in an undergraduate 'Intro to Discrete Structures' course, I
recently did a project which required generating the first n primes. We
discussed the sieve of Eratosthenes in class. Although the professor is
not familiar with Haskell, he allowed me to use it, and I
mistakenly wrote the following code[1]:
-- A list of all prime numbers
primes = [2] ++ [ x | x <- [3..], isPrime x ]
-- x is prime if the set of primes [2 <= p <= sqrt(x)] is empty
isPrime x =
( [] == [ y | y <- (take (intsqrt x) primes), x `mod` y == 0 ] )
This works, and I used it as I developed my project. However, it tests
more primes than necessary. A better version would seem to be:
-- x is prime if the set of prime factors [2 <= p <= sqrt(x)] is empty
isPrime x =
( [] == [ y | y <- (takeWhile (\z -> z <= (intsqrt x)) primes),
x `mod` y == 0 ])
Surprisingly, the second (tight) version grows significantly more costly
than the first (loose) version as we take more primes. Taking 20 primes,
> take 20 primes
both algorithms require under a second. Taking 200 primes, the tight
algorithm requires twice as much time as the loose one. Taking 2000
primes, the tight algorithm requires about 4.5 times as much time as the
loose one.[2]
Can anyone suggest why the tighter algorithm exhibits significantly worse
performance? Is takeWhile significicantly more expensive than take? Is the
\z lambda expression expensive? The intsqrt isn't recalculated each time
takeWhile evalutes a prime, is it?
Slightly confused,
Tim Otten
[1] Note that intsqrt calculates the floor of the square root of x.
intsqrt x = intsqrt' 1 x
intsqrt' n x
| (n*n > x) = n-1
| otherwise = intsqrt' (n+1) x
[2] A few comments on the test apparatus:
* Debian GNU/Linux 3.0
* Hugs98 circa Sept 2001
* Tested on a G3 400mhz and a PII 233mhz. The G3 was consistently
faster, but the relationship (Time(Alg2)/Time(Alg1)) remains
comparable across chips
* Times were established using the bash shell's 'time' command
* Each test was performed in a new instance of 'runhugs'
* Tests were repeated and staggered (Test alg1 @ n primes; test alg2 @ n
primes; test alg1 @ n primes; test alg2 @ n primes)
Codes, scripts, etc. available upon request.
