[Haskell-cafe] Re: FASTER primes

Will Ness will_n48 at yahoo.com
Tue Jan 5 17:16:35 EST 2010

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! :)

More information about the Haskell-Cafe mailing list