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

[Claus Reinke]

> 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 it
closer (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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Sieve.hs
Type: application/octet-stream
Size: 3220 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070225/55ae4aa6/Sieve.obj