Algorithm 10^3 10^4 10^5 10^6 10^7 10^8 Reinke 0.04 1.21 41.00 - - - - Reinke is the ``applyAt'' algorithm Claus Reinke posted here
while I'm not unhappy that this code is performing reasonably well, it was mostly an attempt to get closer to what some perceived as the original sieve specification, with some minor modifications. for performance comparisons, that has the huge disadvantage of having to lug around an increasing ballast of crossed-out numbers. with a straightforward run-length encoding of those zeroes, the code is likely to scale rather better (one dash less, and closer to
Naive;-). there are also some obvious improvements to the folklore sieve that bring itcloser (in spirit, and partially in performance) to the faster versions.
attached is the code for my own experiments, for your entertainment, where folklore: the folklore "sieve" folklore2: without mod, starting (sieve p) from p*p folklore3: merging the sieves, instead of stacking them as implicit thunks genuine: the applyAt version, dubbed "Reinke" genuineRLC: with run-length coding for all those zeroed-out positions dual: the not so "naive", fairly fast one; for reference (speed limit for above)btw, given that the "naive" algorithm performs so well, perhaps it isn't all that naive after all? it does seem to encode the observed effects of nested sieves, without encoding the sieves themselves and their ballast. perhaps there is a corresponding, "dual" version of the wheels as well, eliminating their currently major disadvantage of managing the ever growing wheels in explicit form? for instance, the current
naive/dual algorithm computes the (x `mod` p) from scratch for each x, instead of incrementally from ((x-1)`mod`p). claus
Sieve.hs
Description: Binary data
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
