[Haskell-cafe] how to make haskell faster than python at finding
primes?
Alex Jacobson
alex at alexjacobson.com
Mon Aug 6 03:55:06 EDT 2007
This implementation of calculating 10000 primes (compiled with GHC -O2)
is 25% slower than the naive python implementation. Shouldn't it be
faster? Am I doing something obviously stupid?
primes = map (\(x,_,_)->x) $ filter (\(_,isP,_)->isP) candidates
candidates = (2,True,[]):(3,True,[]): map next (tail candidates)
next (candidate,isP,modCounts) =
let newCounts = map incrMod2 modCounts in -- accumulate mods
(candidate+2 -- we only need to bother with odd numbers
,(isPrime newCounts) -- track whether this one is prime
,if isP then (candidate,2):newCounts else newCounts) -- add if prime
isPrime = and . map ((/=0).snd)
incrMod2 (p,mc) = let mc' = mc+2 in
if mc'<p then (p,mc') else if mc'>p then (p,1) else (p,0)
Note: It is shorter than the python, but I would have assumed that GHC
could deliver faster as well.
-Alex-
More information about the Haskell-Cafe
mailing list