[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was:
Genuine Eratosthenes sieve)
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