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

[Will Ness]

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

> 
> 
> Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness:
> > Now _this_, when tested as interpreted code in GHCi, runs about 2.5x times
> > faster than Priority Queue based code from Melissa O'Neill's ZIP package
> > mentioned at the haskellwiki/Prime_Numbers page, with
> > about half used memory reported, in producing 10,000 to 300,000 primes.
> >
> > It is faster than BayerPrimes.hs from the ZIP package too, in the tested
> > range, at about 35 lines of code in total.
> 
> That's nice. However, the important criterion is how compiled code (-O2)
fares. Do the relations continue to hold? How does it compare to a bitsieve?


Haven't gotten to that part yet. :)

But why is it more important? Would that not tell us more about the compiler
performance than the code itself? 

This code is just an endpoint (so far) in a short procession of natural stepwise
development of the famous classic Turner's sieve, through the "postponed
filters", through to Euler's sieve, the merging sieve (i.e. Richard Bird's) and
on to the tree-fold merging, with wheel. I just wanted to see where the simple
"normal" (i.e. _beginner_-friendly) functional code can get, in a natural way.

It's not about writing the fastest code in _advanced_ Haskell. It's about having
clear and simple code that can be understood at a glance - i.e. contributes to
our understanding of a problem - faithfully reflecting its essential elements,
and because of _that_, fast. It's kind of like _not_ using mutable arrays in a
quicksort.

Seeing claims that it's _either_ Turner's _or_ the PQ-based code didn't feel
right to me somehow, especially the claim that going by primes squares is "a
pleasing but minor optimization", what with the postponed filters (which serves
as the framework for all the other variants) achieving the orders of magnitude
speedup and cutting the Turner's O(n^2) right down to O(n^1.5) just by doing
that squares optimization (with the final version hovering around 1.24..1.17 in
the tested range). The Euler's sieve being a special case of Eratosthenes's,
too, doesn't let credence to claims that only the PQ version is somehow uniquely
authentic and "faithful" to it.

Turner's sieve should have been always looked at as just a specification, not a
code, anyway, and actually running it is ridiculous. Postponed filters version,
is the one to be used as a reference point of the basic _code_, precisely
because it _does_ use the primes squares optimization, which _is_ essential to
any basic sieve.


> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>