This is actually a pretty good algorithm. And also a rather subtle one when it comes to termination. :) -- Lennart On Feb 10, 2007, at 22:00 , apfelmus@quantentunnel.de wrote:
Creighton Hogg wrote:
Hello Haskell-ers, So a friend and I were thinking about making code faster in Haskell, and I was wondering if there was a way to improve the following method of generating the list of all prime numbers. It takes about 13 seconds to run, meanwhile my friend's C version took 0.1. I'd love to learn a bit more about how to optimize Haskell code.
Of course, the best optimization is a better algorithm. In case this is what you're after, have a look at
Colin Runciman, Lazy Wheel Sieves and Spirals of Primes http://citeseer.ist.psu.edu/runciman97lazy.html
While Haskell makes it possible to express very complicated algorithms in simple and elegant ways, you have to expect to pay a constant factor (roughly 2x-10x) when competing against the same algorithm in low- level C.
-- Naive way to calculate prime numbers, testing each new n to see if it has prime factors less than sqrt(n). import Data.List primes = 2:(foldr (\x y -> if isPrime x then x:y else y) [] [3..]) where isPrime x = foldl' (\z y -> z && (if x `mod` y == 0 then False else True)) True (take (floor $ sqrt $ fromIntegral x) primes)
Your code has two glitches and a serious flaw: foldl' is strict but not fast, use foldr instead. Premature strictness is the root of all evil :)
To see what went wrong, I take the freedom to rewrite the code as
primes = 2 : filter isPrime [3..] isPrime x = all' (\p -> x `mod` p /= 0) . take sqrtn $ primes where sqrtn = floor $ sqrt $ fromIntegral n all' prop = foldl' (\z y -> z && prop y) True
The first and most minor glitch is the missing type signature. Every Haskell compiler will default your integers to arbitrary precision Integers:
:t primes [Integer]
I doubt that your C friend uses arbitrary precision arithmetic, so you'd better write down
primes :: [Int] isPrime :: Int -> Bool
The second glitch is that you 'take sqrtn primes'. This is not the same as 'takeWhile (<= sqrtn) primes', i.e. taking primes as long as they are smaller than the square root of n. I guess you know that this results in far fewer primes taken.
The glitches may have been unintentional, but the flaw intentionally degrades performance: you should not use a strict all' but the lazy
all prop = foldr (\y z -> prop y && z) True
from the Prelude. The point is that the lazy version stops inspecting the elements of the remaining list whenever (prop y) turns False for the first time. This is because && is lazy:
False && x = False
for whatever x we supply. For example, take the list
[True, False, True, True] ++ replicate 100 True
Here, all returns False after inspecting the first two elements while all' inspects every one of the 104 list elements just to return False afterwards. As every second number is even, your all' is busy wasting time like crazy.
Regards, apfelmus
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe