[Haskell-cafe] Re: FASTER primes
will_n48 at yahoo.com
Fri Jan 8 12:37:21 EST 2010
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):
> > > 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
"treefold" structure was:
(2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ....... ))))
dpths: 3 4 4 5 5 6 6 7 7 8
(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'
> 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.
More information about the Haskell-Cafe