[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?
> 

OK, I've tested it now. For some reason it runs about 1.3x times slower than
Melissa O'Neill's code when compiled, while taking about the same amount of
memory (going slightly worse actually, 0.97..1.05..1.08), in the range of
100,000..1,000,000..2,000,000 primes produced. The local asymptotic behavior was
about the same, again, in both versions, about O(n^1.20..1.25) - worsening
slightly for the merging version (the ratio of run times going 1.25..1.29..1.32).

I guess that makes the two versions (almost) operationally equivalent in
producing of up to a million primes or two.




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