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

Will Ness will_n48 at yahoo.com
Tue Dec 29 19:23:32 EST 2009

Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> Gee, seems my mail server reads your posts very thoroughly today :)

I hope it's not a bad thing. :)

> Am Dienstag 29 Dezember 2009 14:58:10 schrieb Will Ness:
> >
> > If I realistically needed primes generated in a real life setting, I'd
> > probably had to use some C for that.
> If you need the utmost speed, then probably yes. If you can do with a little
> less, my STUArray bitsieves take about 35% longer than the equivalent C code >
and are roughly eight times faster than ONeillPrimes. I can usually live well >
with that.

Wow! That's fast! (that's the code from haskellwiki's primes page, right?)

> > If OTOH we're talking about a tutorial
> > code that is to be as efficient as possible without loosing it clarity,
> > being a reflection of essentials of the problem, then any overly
> > complicated advanced Haskell wouldn't be my choice either.
> +1
> Though perhaps we view mutable array code differently. In my view, it's
> neither advanced nor complicated.

convoluted, then. Not using "higher level" concepts, like map and foldr, :) or
head.until isSingleton (pairwise merge).map wrap , that kind of thing. :)

BTW I think a really smart compiler should just get a specification, like
Turner's sieve, and just derive a good code from that by itself.

Another example would be

  qq n m = sum $ take n $ cycle [1..m]

which should really get compiled into just a math formula, IMO. Now _that_ I
would call a good compiler. That way I really won't have to learn how to use
STUArray`s you see.

I've seen this question asked a lot, what should be a good programming language?

IMO, English (plus math where needed, and maybe some sketches by hand). :)

> > And seeing that
> > this overly-complicated (IMO), steps-jumping PQ-based code was sold to us
> > as the only "faithful" rendering of the sieve, I wanted to see for myself
> > whether this really holds water.
> I can understand that very well.


More information about the Haskell-Cafe mailing list