[Haskell-cafe] A tale of Project Euler
Don Stewart
dons at galois.com
Tue Nov 27 15:56:56 EST 2007
andrewcoppin:
> 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)
This is an FAQ.
Unless you use the same algorithm and data types in benchmarks, you're
not really benchmarking anything. And expecting one of the worst
possible algorithms to be good is hoping for a little too much :)
When you do use similar data types and algorithms, you get similar
performance:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=all
I'll reiterate: use the same data structures and algorithms, if you want
the same performance.
-- Don
More information about the Haskell-Cafe
mailing list