Albert Y. C. Lai trebla at vex.net
Wed Dec 19 23:34:15 EST 2007

```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

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.

for divisions takes under 11 minutes, and memory slowly grows from 1 MB
to 6 MB.

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