Albert Y. C. Lai
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.
Thanks for all that benchwork (and especially your exponent 61). I must admit, that i ran the (*) version in ghci only (not having compiled it to a standalone version). Maybe ghci is configured wrongly on my system. As i remember, i tried (*) twice, coming near to memory exhaustion and not awaiting the result. I would really like a non-monadic version. What is interesting also is how near your 19 minutes came to my 17 (Windows XP, 2.2GHZ, 512MB). And the comparations to Daniels code seem to imply, that my named fields in DivIter are not very expensive, if at all. Is there documentation of tail recursion anywhere ? I searched (googling with site:www.haskell.org) and didn't find anything else than entries in mailing lists. Cheers, Joost