[Haskell-cafe] A tale of Project Euler

Olivier Boudry olivier.boudry at gmail.com
Tue Nov 27 15:54:26 EST 2007


On 11/27/07, Andrew Coppin <andrewcoppin at btinternet.com> 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<MAX_NUMBERS;m+=n)
>    prime[m]=false;
> }
>
> 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 at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071127/61fb8a1d/attachment.htm


More information about the Haskell-Cafe mailing list