Daniel Fischer
Am Dienstag, 18. Dezember 2007 17:26 schrieb Joost Behrends:
Hi,
since about three weeks i am learning Haskell now. One of my first excercises is to decompose an Integer into its primefactors. I already posted discussion on the solution to the problem 35 in "99 excercises".
My simple algorithm uses a datatype DivIter of 4 named fields together with the core iteration
But a simple recursion that returns the list of primefactors lazily would also solve the stack frame problem, wouldn't it? sort of factor 0 = error "0 has no factorisation" factor 1 = [] factor n | n < 0 = (-1):factor (-n) | even n = 2:factor (n `div` 2) | otherwise = oddFactors 3 n
oddFactors k n | k*k > n = [n] | r == 0 = k:oddFactors k q | otherwise = oddFactors (k+2) n where (q,r) = n `divMod` k
you can then start consuming the prime factors as they come, before the factorisation is complete.
Hi and thanks for your answers, @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. Thus it's vital here, how the recursion is done. Because of that i separated divisions and divstep - for experimenting with divisions. If a factor is done, it should leave as little traces as possible on the machine. Both of your instructions for fix are well readable - thanks again. I'll spend some time studying them, but it seems, fix doesn't fix the problem.