[Haskell-cafe] Re: MonadFix

[Albert Y. C. Lai]

Joost Behrends wrote:
> @Daniel: no, this doesn't solve the stack problem. These are the primefactors of
> 2^120+1: [97,257,673,394783681,4278255361,46908728641]. 
> 
> oddFactors k n | otherwise = oddFactors (k+2) n
> 
> could eventually push 394783681-673 function calls onto the stack before finding
> the factor 394783681. And indeed a recursive version of divisions trying to
> compute this ran more than two hours on my machine, before i stopped it (this is
> the time a python script needs for the computation). And there were peaks of
> memory use > 300 MB ! While the version with the State monad seems to 
> work tail recursive - it has an absolutely constant memory use, slightly
> different per run, i watched 2044k and 2056k. And it takes around 17 minutes on
> my machine getting the result.

Theoretically the recursions in

     oddFactors k n | otherwise = oddFactors (k+2) n

and

(*) divisions y |divisor y <= bound y = divisions (divstep y)

do not cost stack space. They are tail recursions too!

In general similar tail recursions do not cost stack space. Some 
programs using them use a lot of stack space, but that is because of 
non-strictness, not because of tail recursion itself. And such 
non-strictness is absent here due to the way the parameters have to be 
evaluated for all sorts of decisions before further recursive calls.

Empirically my own experiments agree with the theory.

I use GHC 6.8.1, ghc -O2, linux x86, P4 2 GHz, 1 GB RAM.

First I just try 2^61+1 which is more tractable and still challenging 
enough. I think it's a great reference for calibration: it is 
significant enough as a test, and not too long to wait for.

2^61+1 = 3 * 768614336404564651

Your code on
http://www.haskell.org/haskellwiki/?title=Talk:99_questions/31_to_41&oldid=17649
using (*) for divisions takes under 3 minutes and 1.4 MB memory throughout.

Daniel's code takes under 6 minutes and 1.4 MB memory throughout.

Your code using Control.Monad.State (which is Control.Monad.State.Lazy) 
for divisions takes under 11 minutes, and memory slowly grows from 1 MB 
to 6 MB.

Your code using Control.Monad.State.Strict for divisions is similar to 
Control.Monad.State.

Now I try 2^120+1. This probably is six times longer than 2^61+1, so I 
only try your code using (*) and Daniel's code.

Your code using (*) takes under 19 minutes and 1.4 MB memory throughout.

Daniel's code takes 27 minutes and 1.4 MB memory throughout.

I have also tried turning off code optimizations and even deleting 
compiled code and running interpreted code in ghci for a while. I still 
see constant memory usage.

My finding agrees with my theory and disagrees with your finding and 
probably your theory.