Daniel Fischer
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