[Haskell-cafe] Re: FASTER primes

[Will Ness]

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


> So we must make sure that the list of composites that primes' consumes is
> not the same as that which primes'' consumes.


yes that is what I had done too. Duplicated everything. Turns out, it works
exactly as you told it would when using the compiler switch, -fno-cse, thanks!


> > I used the switch; it didn't help at all. The only thing I can see is

wrong. I didn't. When I did, it worked.


> > Unfortunately it grows, as you've said - 23MB for 2 mln. :|
> 
> And I've found out why. Change the definition of tfold to
> 
> tfold f (a: ~(b: ~(c:xs)))
>                      = (a `f` (b `f` c)) `f` tfold f xs
> 
> and memory stays low (things are going much slower, though).


(forced by gmane poster to delete unusually many of your comments today...)

Interesting... As for the structure, I chose it trying to minimize the 
estimated average cost of a composite production, Sum (1/p)*depth. 


> You can make a compromise by using the above tfold (which is no longer a
> tree-fold) and grouping (and merging) the multiples in a slower-growing
> manner,
> .......
> 
> memory still grows, but much slower, in my tests, due to the much smaller
> GC time, it's a bit faster than the version with the original tfold.


Great! :)