You may also like to compare this definition.

> import List
>
> primes = unfoldr sieve [2..]
> sieve (x:xs) = Just (x,filter (x `notDivisor`) xs)
> x `notDivisor` y = y `mod` x /= 0

Slower, but (IMO) cuter.

Cheers,

-----Original Message-----
From: Tim Otten [mailto:tim@cap.american.edu]
Sent: Wednesday, 23 October 2002 15:10
To: haskell-cafe@haskell.org
Cc: scasey@cap.american.edu
Subject: Re: Odd Performance

Tom Pledger writes:

> Probably.  Try replacing this
>    (\z -> z <= (intsqrt x))
> with this
>    (\z -> z^2 <= x)

Yes! This is significantly nicer. Taking 4000 primes, this is about twice
as fast as the original (loose) algorithm, and it appears that it gets
better as n grows. (Call this version #3).

> or moving the O(sqrt(n)) step[1] into a let expression

This does help -- the implementation with this adjustment seems to hover
around 1.1 times the speed of the loose algorithm. (Call this version #4)

> Only if the predicate function (the p in takeWhile p xs) is
> significantly more expensive than a constant-cost piece of arithmetic
> and pattern-matching.

This makes sense and explains the results above: squaring z is easier than
square-rooting x. In fact, the way intsqrt is written, #4's takeWhile
indirectly tests (z*z > x) once for each [z | 1<=z<=sqrt(x)]. #3's
takeWhile expression will only evaluate (z^2 < x) once for each [ z | z <-
primes, z<=sqrt(x) ]. Moreover, #4's takeWhile will do additional tests (z
<= sqrt) for each [z | z <- primes, z <= sqrt(x)]. In retrospect, the
intsqrt-approach seems rather silly. :)

Thank you,
Tim

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe