On Friday 25 June 2010 20:51:44, Vladimir Ch. wrote: > I'm trying to solve this problem: > http://projecteuler.net/index.php?section=problems&id=44, and my > program runs out of memory.
Compile with optimisations. With -O2, after adding fairly naive isSquare and sqrti functions, it seems to run in constant memory (but very slowly, you need a better algorithm, really 8-) ) > I was wondering where I have a space leak, Profiling would tell you where the memory goes. > I thought that this program doesn't accumulate any data structures > (i.e. should use constant memory): > > CODE BEGINS > > -- returns list of pairs (i, j) of indices, for which differences (gen > j - gen i) > -- increase, provided that gen has the following property: > -- gen (i+1) - gen i > gen i - gen (i - 1) > incDiffPairs gen = iterate next (0, 1) > where next (i, j) = if (i == 0) || gen (j+1) - gen > j < gen j - gen (i - 1) > then (j, j + 1) > else (i - 1, j) > > -- returns ith pentagonal number > pentagonal i = let n = i + 1 > in n * (3 * n - 1) `div` 2 > > -- tests if a number is pentagonal > isPentagonal x = let d = 24 * x + 1 > in isSquare d && (1 + sqrti d) `mod` 6 == 0 > > result44 = head [(pentagonal j - pentagonal i, (i, j)) | (i, j) <- > incDiffPairs pentagonal, > isPentagonal (pentagonal j - pentagonal i), > isPentagonal (pentagonal j + pentagonal i)] > > CODE ENDS _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
