[Haskell-cafe] Re: FASTER primes

[Will Ness]

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

> 
> 
> Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus:
> > Will Ness wrote:
> >
> > Hm? In my world view, there is only reduction to normal form and I don't
> > see how "allocate its own storage" fits in there. Okasaki having shown
> > something to that end would be new to me?
> >
> Perhaps what was meant was "storage must be allocated for each filter"
> (which, however, seems trivial).

I still contend that in case of nested filters, where each filter has only one 
consumer, even that isn't ultimately necessary (a chain of pointers could be 
formed). That's because there's no "peek"s, only "pull"s there. If the filters 
are used in merge situation, then there will be some "peek"s so current value 
must be somehow stored, though it's better to be made explicit and thus static 
(the place for it, I mean, instead of the "rolling" cons cell). Such 
implementation technique would prevent some extra gc.


> > > Then under merging these split pairs form a monoid, so can be rearranged
> > > in a tree. If you haven't seen it yet, it uses a different folding
> > > structure to your code, with a lower total cost of multiples production
> > > (estimated as Sum (1/p)*depth):

correction:

> > >  tfold f (x:y:z:xs) = (x `f` (y `f` z)) `f` tfold f (pairwise f xs)
> > >  comps = tfold mergeSP $ pairwise mergeSP multips
> >
> > The idea being that each prime produces  1/p  composites each "turn" and
> > it takes time  depth  to trickle it to the top? Sounds reasonable, but
> > remember that a prime  p  does not start to generate composites until
> > the "turn count" has reached p^2, so it might occupy a place of low
> > depth in the tree that is better spent on the previous primes. 


That might be why Daniel's structure is better: it plunges down faster than 
mine.


"treefold" structure was:
        (2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ....... ))))
dpths:   3 4       4 5       5 6        6  7        7  8


daniel's:
    (2+(4+6)) + ( (8+(10+12)) + ( (14+(16+18)) + ( (20+(22+24)) + .... ))
     3  5 5.4      6  7.8 7.9      8   9  9.5     9.6 10.7 10.8



> primes () = 2:3:5:7:11:13:primes'
>    where
>     primes'   = roll 17 wheel13 `minus` compos primes'''
>     primes''  = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes''
>     primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes''


Haven't read through the whole thing yet. :) :) I thought there was a typo 
there. There isn't.

BTW using the no-share switch isn't necessary if we just write it down twice 
with some variations, like 

      primes''' = let (h,t)=span (< 17^2) roll 17 wheel13
                  in h++t `minus` compos primes''

As we've found out, compilers aren't  _that_ smart yet.