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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
