Daniel Fischer <daniel.is.fischer <at> web.de> writes: > > 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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
