Re: [Haskell-cafe] A tale of Project Euler

On 11/27/07, Andrew Coppin wrote:

Hi guys.

Somebody just introduced me to a thing called "Project Euler". I gather it's well known around here...

Anyway, I was a little bit concerned about problem #7. The problem is basically "figure out what the 10,001st prime number is". Consider the following two programs for solving this:

First, somebody else wrote this in C:

int n = 2 , m , primesFound = 0;

for( n=0;n < MAX_NUMBERS;n++ ) if( prime[n] ) { primesFound++;

if( primesFound == 10001 ) cout << n << " is the 10001st prime." << endl;

for(m=2*n;m

Second, my implementation in Haskell:

primes :: [Integer] primes = seive [2..] where seive (p:xs) = p : seive (filter (\x -> x `mod` p > 0) xs)

main = print (primes !! 10000)

Well, we know who's winning the beauty contest. But here's the worrying thing:

C program: 0.016 seconds Haskell program: 41 seconds

Eeeps! o_O That's Not Good(tm).

Replacing "primes :: [Integer]" with "primes :: [Word32]" speeds the Haskell version up to 18 seconds, which is much faster but still a joke compared to C.

Running the Haskell code on a 2.2 GHz AMD Athlon64 X2 instead of a 1.5 GHz AMD Athlon drops the execution time down to 3 seconds. (So clearly the box I was using in my lunch break at work is *seriously* slow... presumably the PC running the C code isn't.)

So, now I have a Haskell version that's "only" several hundred times slower. Neither program is especially optimised, yet the C version is drastically faster. This makes me sad. :-(

By the way... I tried using Data.List.Stream instead. This made the program about 40% slower. I also tried both -fasm and -fvia-c. The difference was statistically insignificant. (Hey guys, nice work on the native codegen!) The difference in compilation speed was fairly drastic though, needless to say. (The machine is kinda low on RAM, so trying to call GCC makes it thrash like hell. So does linking, actually...)

Also, I'm stuck with problem #10. (Find the sum of all primes less than 1 million.) I've let the program run for well over 15 minutes, and still no answer is forthcomming. It's implemented using the same primes function as above, with a simple filter and sum. (The type has to be changed to [Word64] to avoid overflowing the result though.) The other guy claims to have a C solution that takes 12 ms. There's a hell of a difference between 12 ms and over half an hour...(!) Clearly something is horribly wrong here. Uh... help?

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

Hi Andrew, I don't remember who I stole this prime computation from, but it is very fast (10001's prime in 0.06 sec with Int and 0.2 with Integer on my machine) and not overly complex: primes :: [Integer] primes = 2 : filter (l1 . primeFactors) [3,5..] where l1 (_:[]) = True l1 _ = False primeFactors :: Integer -> [Integer] primeFactors n = factor n primes where factor _ [] = [] factor m (p:ps) | p*p > m = [m] | m `mod` p == 0 = p : factor (m `div` p) (p:ps) | otherwise = factor m ps I used it a lot while playing with Euler Project. Many of the problems require prime calculation. Cheers, Olivier.