[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

Melissa O'Neill oneill at cs.hmc.edu
Sat Feb 24 21:40:24 EST 2007

Someone asked if I'd include a "classic C" version of the Sieve in my  
comparisons.  Having done so, Lennart wrote (slightly rephrased):
> How did you compare the C version with the Haskell versions? The  
> Haskell programs produce the Nth prime, whereas the C code produces  
> the last prime less than M.

True.  But since I have to know what M is to find the Nth prime, it's  
easy enough to ask the C code to produce the right prime.

> To make the C code to what the Haskell code does you need to set  
> some upper bound that is related to the prime number distribution.   
> I see no trace of this in your code.

The Haskell versions that go up to a limit do this, so I could easily  
have written code to do it -- it's not hard, but has no real bearing  
on the time complexity of the code, so I didn't bother.

You could argue that it's cheating to tell it so blatantly when to  
stop, but I hate the C code I'd found enough that I didn't really  
want to touch it any more than I had to.

A much more legitimate complaint about the comparison with the C code  
is actually on space usage.  It uses much more space than some of the  
algorithms it's competing with.  More about that in an upcoming message.


More information about the Haskell-Cafe mailing list